数据结构二叉树,数据结构与算法（3）——二叉堆
#include
using namespace std;
const int HEAP_SIZE = 100;
void sink(int fa);
void swim(int son); int heap[HEAP_SIZE+1];
int hs;
//以建立最小堆为例 /*****************************************************************/
//删除堆顶元素 ，利用上游函数调整
/*
删除最小值(deleteMin) 先用最后一个元素代替根
由于这一步会导致根的元素比儿子大，因此需要向下调整。向下调整的方法很简
单，就是把根和较小儿子做比较，如果根比较大，则交换它和儿子，算
法好比石沉大海，因此有的书把它称为sink过程
*/
int deleteMin(){ int value = heap[1]; //把堆尾元素前置，再sink(）调整 heap[1]=heap[hs--]; sink(1); cout<>1,a = heap[son]; while(fa&&heap[son]>1; } heap[son] = a;
} /*****************************************************************/
//初始建立一个堆
/*
给hs个整数，如何构造一个二叉堆？可以一个一个插入，但是有更好
的方法：从下往上一层一层向下调整。由于叶子无需调整，因此只需
要从[hs/2] 开始递减到1。
*/
void build(){ for(int i=hs/2;i>=1;i--) sink(i);
} int main(){ cin>>hs; for(int i=1;i<=hs;i++) cin>>heap[i]; build(); cout<<"删除最小元素："< 二叉堆(binary heap) 是一个高级数据结构，它的思想简单，代码短，然而用处非常大。二叉堆一般被用来实现优先队列(priority queue)
优先队列经常被用来实现贪心算法和离散时间模拟系统，是一个基础数据结构。STL专门提供了priority queue 容器适配器，读者可以在学习本节后比较它和自己的二叉堆实现法的效率。二叉堆是一棵完全二叉树，即所有叶子在同一层，且集中在左边。二叉堆满足堆性质(heap property) ：根的值在整棵树中是最小的。不仅如此，根的两棵树分别构成堆。用heap 数组来表示各个元素，则根是heap[1] ，最后一个元素是heap[n] （ heap[0]不使用）。
k 的左儿子是2k ，右儿子是2k + 1 ，父亲是bk=2c 。
延伸阅读
最新评论