学步园

前记：

被大神们特别强调的一种数据结构，可以高效地维护，工作中常见，so，重视。

Tips：

1.添加元素总是从叶子添，删除元素总是从根删；

2.添加元素体现“上浮”赶脚，删除元素体现“下沉”赶脚，所以一般一个叫 heapFixUp，一个叫heapFixDown；

Codes（来自白话经典算法系列）：

1.添加元素

void minHeapFixUp(int a[], int i)
{
	for (int j = (i - 1) / 2; (j >= 0 && i != 0) && a[i] < a[j] ; i = j, j = (i - 1) / 2)
	{
		swap(a[i], a[j]);
	}
}

void add2Heap(int a[], int n, int num)
{
	a[n] = num;
	minHeapFixUp(a, n);
}

2.删除元素

void minHeapFixDown(int a[], int i, int n)   //n 为节点总数
{
	int j = 2 * i; 					//根从下标1开始算，0的话再+1

	while(j < n)
	{
		if (a[j] > a[j + 1])    //左右儿子找小的
		{
			j++;
		}
		if (a[i] < a[j])
		{
			break;
		}
		swap(a[i], a[j]);
		i = j;
		j = 2 * i;
	}
}

void deleteNumInHeap(int a[], int n)
{
	swap(a[1], a[n]);
	minHeapFixDown(a, 1, n - 1);
}

3.建立堆

void bulidMinHeap(int a[], int n) 
{
	for (int i = n / 2 - 1; i > 0; --i)      //叶子已经是合法堆,从最后一片叶子的爹调起。ps：堆形状约等于满二叉树。
	{
		minHeapFixDown(a, i, n);
	}
}

4.堆排序

void heapsort(int a[], int n)
{
	int i;
	buildMinHeap(a, n);
	for (i = n; i > 0; --i)
	{
		swap(&a[1], &a[i]);
		minHeapFixDown(a, 1, i);
	}
}