二叉堆 顶堆

1. 适用范围:

1. 堆排序

2. 相关概念:

2.1. 大树枝序列

从根结点开始,每次都沿着大的孩子往下走,从上往下的路径构成大树枝序列

3. 梗概:

大顶堆: 一种特殊的完全二叉树, 根结点大于等于左右孩子 小顶堆: 一种特殊的完全二叉树 根结点小于等于左右孩子

4. 操作:

1. 把数组改造成大顶堆/创建大顶堆
   1. 算法思想: 类似插入排序, 从最后一个非叶结点开始, 把每个结点的大树枝序列排为降序

5. 性质:

1. 大顶堆性质:
   1. 为大顶堆 ⇐> 每个结点的大树枝序列都为降序
   2. 根结点的大树枝序列 == 根结点 + 较大子树的大树枝序列

6. 在c语言中的实现

6.1. 定义:

梗概:

1. 按照层序顺序, 用数组存储每个结点, 其中下标0不使用
   1. 因为是完全二叉树, 所以非常适合使用数组存储, 可以利用层序编号得到孩子与双亲结点 代码:

typedef struct{
    KeyType key;
}RecordType;
RecordType r[记录长度];

6.2. 把数组改造成大顶堆/创建大顶堆

代码:

/*相位差,以便把Records[1...len]映射为
Records[1-PHASE...len-PHASE]*/
#define PHASE 1
void sift(RecordType Records[],int root, int tailLeaf);
void crt_heap(RecordType Records[],int len){
//需要传入下标0已使用的普通记录数组
    len+=PHASE;//把普通数组看成二叉堆
    /*类似插入排序,从大树枝序列长度为2开始*/
    /*该for结合了插入排序指针推进与遍历所有大树枝序列*/
	for(int i=len>>1;i>=1;--i)sift(Records,i,len);
}
 
void sift(RecordType Records[],int root, int tailLeaf){
//沿着根结点每次沿着大的孩子往下走,从上往下路径构成大树枝序列
//现在大树枝序列除了根结点,都是降序的,需要把根结点插入排序到降序的大树枝序列中
/*类似于插入排序,把根结点插入到大树枝序列中*/
	RecordType temp=Records[root-PHASE];//空出位置
	int parent=root;
	int Child=2*parent;
	for(;Child<=tailLeaf;){
		if(Child+1<=tailLeaf&&
        Records[Child-PHASE].key<Records[Child+1-PHASE].key)
			++Child;//大树枝序列要求每次都去大的分支
		if(temp.key>=Records[Child-PHASE].key)
			break;//找到了根结点应该插入的位置
		else {
			/*往上移动比根结点大的结点,为根结点腾位置*/
			Records[parent-PHASE]=Records[Child-PHASE];
			//此时Child指向空位
			parent=Child;//进入下一层子树
			//此时parent指向空位
			Child=2*parent;
		}
	}
    /*把根结点放在腾出来的,属于它的空位*/
	Records[parent-PHASE]=temp;//parent位置必定是空的
}