关于算法:堆排序

5次阅读

共计 1340 个字符，预计需要花费 4 分钟才能阅读完成。

在堆排序算法中，应用的是最大堆，最小堆通常用于结构优先队列。

如果咱们应用指针来示意堆有序的二叉树，那么每个元素都须要 3 个指针来找到它的高低结点（父结点和两个子节点各须要一个）。但如果应用齐全二叉树来示意二叉堆，则只须要数组而不须要指针皆能够示意。具体方法就是将二叉树的结点依照 层级程序 放入数组中，根结点在地位 1 [不应用数组的第一个地位 0]。则结点 k 的父结点为 k /2，两个子结点地位为 k *2、k*2+1。

数组实现（无序）insert 和栈的 push()操作统一；del 须要增加一段相似于抉择排序的内循环找到最大元素并删除
数组实现（有序）insert 须要将所有较大元素向右挪动以使数组放弃有序；del 和栈的 pop()操作统一

上述两种高级计划中，插入元素和删除最大元素这两个操作之一在最坏状况下须要线性工夫来实现。
应用无序序列是解决问题的惰性办法，仅在必要的时候才会采取行动（找到最大元素）；应用有序序列则是解决问题的踊跃办法，因为会尽可能防患未然（在插入元素时就放弃列表有序），使后序操作更高效。

上浮：如果堆的有序状态因为某个结点变得比它的父结点更大而突破，那么就须要通过替换它和它的父结点来修复堆。

void swim(int nums[], int k, int n) {while (k > 1 && nums[k / 2] < nums[k]) {swap(nums[k / 2], nums[k]);
        k = k / 2;
    }
}

下沉：如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被突破了，那么就须要通过将它和它的 两个子结点中的较大者 替换来修复堆。

void sink(int nums[], int k, int n) {while (k * 2 <= n) {
        int j = k * 2;
        if (j < n && nums[j] < nums[j + 1]) j++;
        if (!(nums[k] < nums[j])) break;
        swap(nums[k], nums[j]);
        k = j;
    }
}

堆排序之前首先须要将 N 个元素的数组结构一个堆。当然能够在 O(NlogN)工夫内，从左至右遍历数组，用 swim()保障左侧的元素曾经堆有序。更高效的方法是从右至左用 sink()办法结构子堆。因为当用数组示意存储 n 个元素的堆时，叶结点下标别离是 n /2 + 1, n/2 + 2, ... , n。每个叶结点都能够看成是只蕴含一个元素的堆。故这部分曾经堆有序，咱们只须要从 n / 2 开始往前遍历一半元素，调用 sink()，直到下标 1 即可。工夫复杂度为 O(NlogN)。

for (int k = n / 2; k >= 1; k--) {sink(nums, k, n);
}

构建完最大堆之后，将堆中的最大元素删除，而后放入堆放大后数组中空出的地位。这个过程和抉择排序相似（依照降序取出所有元素），但所需的比拟要少得多，因为堆提供了一种从未排序局部找到最大元素的无效办法。

void heap_sort(int nums[], int n) {for (int k = n / 2; k >= 1; k--) {sink(nums, k, n);
    }
    while (n > 1) {swap(nums[1], nums[n--]);
        sink(nums, 1, n);
    }
}

堆排序不是稳固的；是原地排序；工夫复杂度为 O(NlogN)，空间复杂度为 O(1)。

正文完