Go Through算法导论:堆和堆排序

2016年01月19日 原创
关键词: C++ 数据结构 算法导论
摘要 本文介绍了什么是堆以及堆排序的实现。

(二叉)堆是一个数组,它可以被看成一个近似的完全二叉树。书上的每一个节点对应数组中的一个元素。除了最底层外,该树是完全充满的,而且是从左向右填充。表示堆的数组A包括两个属性:A.length(通常)给出数组元素的个数,A.heap-size表示有多少个堆元素存储在该数组中。也就是说,虽然A[1..A.length]可能都存有数据,但只有A[1..A.heap-size]中存放的是堆的有效元素。

父节点

parent(i)

return i/2

左孩子

left(i)

return 2*i

右孩子

right(i)

return 2*i+1

二叉堆可以分为两种形式:最大堆最小堆。最大堆是指除了根以外的所有结点都不比父节点大。最小堆则是指除了根以外的所有结点都不比父节点小。

下面是把数组中的一个元素加入到最大堆里的伪代码

MAX-HEAPIFY(A,i)

  l=LEFT(i)

  r=RIGHT(i)

  if l ≤A.heap-size and A[l] > A[i]

    largest=l

  else largest = i

  if r ≤ A.heap-size and A[r] > A[largest]

    largest=r

  if largest ≠ i

    exchange A[i] with A[largest]

    MAX-HEAPIFY(A,largest)

MAX-HEAPIFY使得i及其孩子和孩子的子树都满足最大堆的性质。

建堆

我们可以用自底向上的方法利用过程MAX-HEAPIFY把一个大小为n=A.length的数组转换为最大堆。

BUILD-MAX-HEAP(A)

  A.heap-size = A.length

  for i = A.length/2 downto 1

    MAX-HEAPIFY(A,i)

堆排序算法

初始时候,堆排序算法利用BUILD-MAX-HEAP将输入数组A[1..n]建成最大堆,其中n=A.length。因为数组中最大元素总是在根节点A[1]中,通过把它与A[n]进行互换,我们可以让该元素放到正确的位置。这时候,如果我们从堆中去掉结点n(这一操作通过减少A.heap-size的值来实现),剩余的节点中,原来根的孩子结点仍然是最大堆,而新的根节点可能会违背最大堆的性质。为了维护最大堆的性质,我们要做的是调用MAX-HEAPIFY(A,1),从而在A[1..n-1]上构造一个新的最大堆。堆排序算法会不断重复这一过程,直到堆的大小从n-1降到2。

HEAPSORT(A)

  BUILD-MAX-HEAP(A)

  for i = A.length downto 2

    exchange A[1] with A[i]

    A.heap-size = A.heap-size - 1

    MAX-HEAPIFY(A,1)

堆排序算法的时间复杂度是O(nlogn),因为每次调用BUILD-MAX-HEAP的时间复杂度是O(n),而n-1次调用MAX-HEAPIFY,每次时间是O(logn)。

下面是堆排序的C++代码

#include<iostream>
using namespace std;
int left(int i) { return 2 * i; }
int right(int i){ return 2 * i + 1; }
class Heap{
public:
    int *arr;
    int arrSize;
    int heapSize;
    Heap(int* arr, int arrSize) :arr(arr), arrSize(arrSize){}
};
void maxHeapify(Heap& h, int i) {
    int l = left(i);
    int r = right(i);
    int largest = 0;
    if (h.arr[l] > h.arr[i]&&l<h.heapSize) {
        largest = l;
    }
    else {
        largest = i;
    }
    if (h.arr[r] > h.arr[largest]&&r<h.heapSize) {
        largest = r;
    }
    if (largest != i) {
        swap(h.arr[i], h.arr[largest]);
        maxHeapify(h, largest);
    }
}
void buildMaxHeap(Heap& h) {
    h.heapSize = h.arrSize;
    for (int i = h.arrSize / 2; i >= 0; i--) {
        maxHeapify(h, i);
    }
}
void heapsort(Heap &h) {
    buildMaxHeap(h);
    for (int i = h.arrSize - 1; i > 0; i--) {
        swap(h.arr[i], h.arr[0]);
        h.heapSize--;
        maxHeapify(h, 0);
    }
}
int main() {
    int arr[] = { 16, 4, 10, 14, 17, 9, 3, 2, 8, 100 };
    Heap h(arr, sizeof(arr) / sizeof(int));
    heapsort(h);
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

程序运行结果: