堆的原理及实现

1 堆的原理

先看一下堆长什么样：

最大堆的特点：

1. 每个结点最多可以有2个子结点。
2. 根结点的键值是所有堆结点值中的最大者，且每个结点的值都比其孩子的值大。
3. 除了根结点没有兄弟结点，最后一个左子结点可以没有兄弟结点，其他结点必须有兄弟结点。

看一下如下几个符不符合最大堆的定义：

（A、B不是，C是最大堆。）

看一下堆的特点：

• 堆是你见过的最有个性的树！它是用数组表示的树！
  

对于i子结点：

• i的左子结点为：2 * i + 1
• i的右子结点为：2 * i + 2
• i的父结点：(i - 1) / 2

---

2 堆的实现

2.1 堆的创建

在数组中快速创建堆：

算法实现如下：

堆数据结构的定义：

#define DEFAULT_CAPCITY 128

typedef struct _Heap{
	int *arr; //存储堆元素的数组
	int size; //当前已存储的元素个数
	int capacity; //当前存储的容量
}Heap;

建最大堆：

bool initHeap(Heap &heap, int *orginal, int size);
static void buildHeap(Heap &heap);
static void adjustDown(Heap &heap, int index);

/*初始化堆*/
bool initHeap(Heap &heap, int *orginal, int size){
	int capacity = DEFAULT_CAPCITY>size? DEFAULT_CAPCITY:size;

	heap.arr = new int[capacity];
	if(!heap.arr) return false;

	heap.capacity = capacity;
	heap.size = 0;

	//如果存在原始数据则构建堆
	if(size>0){
		memcpy(heap.arr, orginal, size*sizeof(int));
		heap.size = size;
		buildHeap(heap);
	}else {
		heap.size = 0;
	}

	return true;
}

/*将当前的节点和子节点调整成最大堆*/
void adjustDown(Heap &heap, int index)
{ 
	int cur=heap.arr[index];//当前待调整的节点
	int parent,child;

	/*判断否存在大于当前节点子节点，如果不存在 ，则堆本身是平衡
	的，不需要调整；如果存在，则将最大的子节点与之交换，交换后，
	如果这个子节点还有子节点，则要继续按照同样的步骤对这个子节点进行调整
	*/
	for(parent=index; (parent*2+1)<heap.size; parent=child){
		child=parent*2+1;

		//取两个子节点中的最大的节点
		if(((child+1)<heap.size)&&(heap.arr[child]<heap.arr[child+1])){
			child++;
		}

		//判断最大的节点是否大于当前的父节点
		if(cur>=heap.arr[child]){//不大于，则不需要调整，跳出循环
			break;
		}else {//大于当前的父节点，进行交换，然后从子节点位置继续向下调整
			heap.arr[parent]=heap.arr[child];
			heap.arr[child]=cur;
		}
	}
}

/* 从最后一个父节点(size/2-1 的位置)逐个往前调整所有父节点
（直到根节点）,确保每一个父节点都是一个最大堆，最后整体上形成一个最大堆 */
void buildHeap(Heap &heap){
	int i;

	for(i=heap.size/2-1; i>=0; i--){
		adjustDown(heap, i);
	}
}

---

参考资料：

1. C/C++从入门到精通-高级程序员之路【奇牛学院】