首页 > 代码库 > 堆以及堆排序
堆以及堆排序
1. 堆
二叉堆是一个数组，它可以被看成一个近似的完全二叉树。
二叉堆有两种形式:最大堆和最小堆。在最大堆中，父节点的值总是大于等于任何一个子节点的值。因此，堆中的最大元素放在根节点中，并且在任一子树中，该字数包含的所有节点的值都不大于该子树根节点的值。最小堆是指父节点的值总是小于或等于任一子节点的值。
在堆排序算法中，我们使用最大堆。最小堆通常用于构造优先队列。
2.堆的存储
一般都用数组来表示堆。一般位置0不用来存储元素，即存储区域为A[1,...,len]。所以对于一个节点。它的父节点的下标为2/i，左孩子的下标为2*i，右孩子的节点为2*i+1.
如果要使用下标为0的位置，那么父节点的下标就为(i-1)/2。它的左右子节点下标为2*i+1和2*i+2。
本文中将不使用0位置。
3. 向下调整
向下调整是为了维护堆的性质。它的输入为数组A和下标i。它首先看该节点是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换。交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到该节点为根的子结构成堆为止。时间复杂度为O(lgn)
1 void AdjustDown(ElemType A[], int k, int heap_size) { 2 int child; 3 ElemType tmp = A[i]; 4 5 for (int i = k << 1; i <= heap_size; i *= 2) { // 沿键值较大的子节点向下筛选 6 if (i < heap_size && A[i + 1] > A[i]) { 7 i++; 8 } 9 if (A[child] < tmp) {10 A[k] = A[child]; //将A[child]调整到双亲的位置11 k = i; //修改键值,以便继续向下筛选12 } else {13 break;14 }15 16 }17 18 a[k] = tmp; //被筛选的值放入最终的位置19 }
算法导论中给出的递归的方法：
1 inline int Left(int i) { 2 return i << 1; 3 } 4 5 inline int Right(int i) { 6 return i << 1 + 1; 7 } 8 9 void AdjustDown(int A[], int k, int heap_size) {10 int left_child = Left(k);11 int right_child = Right(k);12 13 int largest = k;14 15 if (left_child <= heap_size && A[left_child] > A[largest]) {16 largest = leftc_child;17 }18 if (right_child <= heap_size && A[right_child] > A[largest]) {19 largest = right_child;20 }21 22 if (largest != k) {23 swap(A[k], A[largest]);24 AdjustDown(A, largest, heap_size);25 }
4.建堆
可以使用
堆以及堆排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。