《算法导论》第6章 堆排序 个人笔记

第6章 堆排序

6.1 堆

最大堆：A[PARENT(i)]>=A[i] 最小堆：A[PARENT(i)]<=A[i]

6.2 维护堆的性质

void HeapAdjust(int H[],int s, int length) { int tmp = H[s]; int child = 2*s+1; //左孩子结点的位置。(i+1)为当前调整结点的右孩子结点的位置 while (child < length) { if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点) ++child ; } if(H[s]<H[child]) { // 如果较大的子结点大于父结点 H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点 s = child; // 重新设置s ,即待调整的下一个结点的位置 child = 2*s+1; } else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出 break; } H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上 }

6.3 建堆

void BuildingHeap(int H[], int length) { //最后一个有孩子的节点的位置 i = (length -1) / 2 for (int i = (length -1) / 2 ; i >= 0; --i) HeapAdjust(H,i,length); }

6.4 堆排序

void HeapSort(int H[], int length) { //初始堆 BuildingHeap(H, length); //从最后一个元素开始对序列进行调整 for (int i = length - 1; i > 0; --i) { //交换堆顶元素H[0]和堆中最后一个元素 int temp = H[i]; H[i] = H[0]; H[0] = temp; //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整 HeapAdjust(H, 0, i); } }

6.5 优先队列

HeapExtractMax：去掉并返回S中的具有最大键字的元素 int HeapExtractMax(int H[], int length) { if (length < 1) return -1; int max = H[0]; H[0] = H[length-1] HeapAdjust(H, 0, length - 1) return max; } HeapIncreaseKey：将元素x的关键字值增加到key void HeapIncreaseKey(int H[], int length, int i, int key) { if (key < H{i]) return; H[i] = key while (i > 0 && H[(i-1)/2] < H[i]){ H[i] = H[(i-1)/2]; H[(i-1)/2] = key; i = (i-1)/2; } } MaxHeapInsert：将新元素x插入到集合S中 int[] MaxHeapInsert(int H[], int length, int key){ int newH[] = new int[length + 1]; for (int i = 0; i <= length; i++) newH[i] = H[i]; newH[length] = -1; length++; HeapIncreaseKey(H, length, length - 1, key); }