大家好，欢迎来到IT知识分享网。
-
Heap是一种数据结构具有以下的特点：
1）完全二叉树；
2）heap中存储的值是偏序； -
Min-heap: 父节点的值小于或等于子节点的值；
Max-heap: 父节点的值大于或等于子节点的值；
-
堆的存储：
一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
-
堆的操作：insert
插入一个元素：新元素被加入到heap的末尾，然后更新树以恢复堆的次序。
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中。
-
堆的操作：Removemax
按定义，堆中每次都删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最大的，如果父结点比这个最小的子结点还大说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。
-
堆的操作：buildHeap 堆化数组
对于叶子节点，不用调整次序，根据满二叉树的性质，叶子节点比内部节点的个数多1.所以i=n/2 -1 ，不用从n开始。
-
堆排序
堆建好之后堆中第0个数据是堆中最大的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最大的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/34962.html
