转载

堆和堆排序

在讨论「堆排序」之前，先复习一下「选择排序」。

void SelectionSort(int a[], size_t n) {   for (size_t i = 0; i < n; ++i) {     // 在剩余元素中找出最小的一个，然后与 a[i] 交换。     size_t k = i;     for (size_t j = i+1; j < n; ++j) {       if (a[j] < a[k]) {         k = j;       }     }      if (k != i) {       std::swap(a[i], a[k]);     }   } }

选择排序的空间效率很高（ O(1) ），但是时间效率很低（ O(N^2) ），主要花在了「从剩余元素中找出最小元素」，每次都要遍历剩余的全部元素。

有没有一种数据结构，能够方便的拿到最小元素？

如果重写 SelectionSort ，改为反向遍历，每次「从剩余元素中找出最大元素」：

void SelectionSort(int a[], size_t n) {   for (size_t i = n-1; i > 0; --i) {     // 在剩余元素中找出最大的一个，然后与 a[i] 交换。     size_t k = i;     for (size_t j = 0; j < i; ++j) {       if (a[j] > a[k]) {         k = j;       }     }      if (k != i) {       std::swap(a[i], a[k]);     }   } }

那么问题就可以改成：有没有一种数据结构，能够方便的拿到最大元素？

堆，就是这样一种数据结构。

其实堆有「最大堆」和「最小堆」之分，但是差别不大，这里以最大堆为例，是为了便于实现堆排序，这也是改写 SelectionSort 的原因。

堆是一种在数组上实现的几乎完全的二叉树，子节点小于父节点，所以根节点总是最大。

记 H[1..n] 为堆，以 H[i] 表示数组中第 i 个元素，它的父节点位于 i/2 ，子节点分别位于 i*2 和 i*2+1 。

这种通过数组下标的关系来连接父子节点的方式，比一般的树型节点省了两个指针的空间。

给定一个堆 [ 30, 26, 13, 17, 11, 7, 8, 10, 4, 3 ] ，那么对应的树型结构为：

                30             /      /          26          13       /     /      /   /      17      11   7     8    /   /    /  10     4  3

假如有一个数组 [ 4, 3, 7, 10, 11, 13, 8, 26, 17, 30 ] ，怎么把它转换成堆呢？

              4            /      /          3          7       /     /    /    /     10      11  13     8   /   /    /  26   17  30

从最小最靠近叶节点的子树开始，如果根节点比子节点小，就与之交换，依次按如下步骤进行调整。

第一步：

   11*             30   /       -->     /  30             11*

第二步：

    10*            26   /   /   -->    /   /  26   17        10*   17

第三步：

    7*             13   /   /   -->    /   /  13    8        7*    8

第四步：

         3*       /     /      26      30    /   /    /   10   17  11  -->          30       /     /      26      3*    /   /    /  10    17  11  -->          30       /     /      26      11    /   /    /  10    17  3*

第五步：

              4*            /      /          30        13       /     /     /  /      26      11  7    8    /   /    /  10    17  3  -->               30            /      /          4*        13       /     /     /  /      26      11  7    8    /   /    /  10    17  3  -->               30            /      /          26        13       /     /     /  /      4*      11  7    8    /   /    /  10    17  3  -->               30            /      /          26        13       /     /     /  /      17      11  7    8    /   /    /  10    4*  3

经过这五步，堆就建好了。下面以 C++ 代码示范。

MakeHeap 把一个数组转换成堆：

void MakeHeap(A& a) {   for (size_t i = a.size() / 2; i > 0; --i) {     SiftDown(a, a.size(), i);   } }

类型 A 就是 std::vector 。当然用 C 数组也可以，只是后续讨论插入操作时会比较麻烦。

typedef std::vector<int> A;

MakeHeap 通过 SiftDown 把每棵子树的根节点向下调整。

// SiftDown 把堆 h[1..n] 的第 i 个元素向下调整（i 从 1 打头）。 void SiftDown(A& h, size_t n, size_t i) {   while (true) {     i = i * 2;      if (i > n) {       break;     }      if (i < n && h[i] > h[i-1]) {       ++i;     }      if (h[i-1] > h[i/2-1]) {       std::swap(h[i-1], h[i/2-1]);     } else {       break;     }   } }

MakeHeap 的用法：

int data[10] = { 4, 30, 8, 17, 26, 13, 7, 3, 10, 11 }; A a(data, data + 10); MakeHeap(a);

堆排序：

void HeapSort(A& a) {   MakeHeap(a);  // 首先把数组 a 转换成堆。    // 反向遍历，每次把堆的根与第 i 个元素交换。   // 每次交换后，用 SiftDown 把新的根向下调整。   for (size_t i = a.size(); i > 1; --i) {     std::swap(a[0], a[i-1]);     SiftDown(a, i-1, 1);   } }

堆排序与选择排序极为相似，空间效率一样，时间效率更优（ O(N*logN) ）。

与 SiftDown 相反的操作为 SiftUp 。

// SiftUp 把堆 h[1..n] 的第 i 个元素向上调整（i 从 1 打头）。 void SiftUp(A& h, size_t i) {   while (i > 1) {     if (h[i-1] > h[i/2-1]) {       std::swap(h[i-1], h[i/2-1]);     }     i = i / 2;   } }

插入操作依赖于 SiftUp ：先添加到数组末尾，然后通过 SiftUp 把新元素向上调整。

void Insert(A& h, int x) {   h.push_back(x);   SiftUp(h, h.size()); }

删除操作依赖于 SiftDown ：先把要删除的第 i 个元素与最后一个元素交换，然后收缩数组，再通过 SiftDown 把交换上来的元素向下调整。

void Delete(A& h, size_t i) {   size_t n = h.size();    if (n == 0 || i == 0 || i > n) {     return;   }    if (i == n) {     h.resize(n - 1);     return;   }    std::swap(h[i - 1], h[n - 1]);   h.resize(n - 1);   SiftDown(h, n - 1, i); }

原文 http://segmentfault.com/a/1190000004363860

正文到此结束