Go Through算法导论:优先队列

2016年01月19日 原创
关键词: C++ 数据结构 算法导论
摘要 本文介绍了如何基于最大堆实现最大优先队列。

优先队列是一种用来维护由一组元素构成的集合S的数据结构,其中的每一个元素都有一个相关的值,称为关键字(key)。优先队列由堆这种数据结构来实现,这里假设您已经明白了堆的实现。如果对堆仍有问题,可以再看看Go Through算法导论:堆和堆排序

优先队列和堆一样有两种形式:最大优先队列和最小优先队列。这里我们关注与如何基于最大堆实现最大优先队列。一个最大优先队列应该支持以下的操作:

  • INSERT(S,x):把元素x插入集合S中。
  • MAXIMUM(S):返回S中具有最大关键字的元素。
  • EXTRACT-MAX(S):去掉并返回S中的具有最大关键字的元素。
  • INCREASE-KEY(S,x,k):将元素x的关键字值增加到k,这里假设k的值不小于x的原关键字值。

过程HEAP-MAXIMUM可以在Θ(1)时间内完成

HEAP-MAXIMUM(A)

  return A[1]

过程HEAP-EXTRACT-MAX可以在Θ(lgn)完成

HEAP-EXTRACT-MAX(A)

  if A.heap-size < 1

    error "heap underflow"

  max = A[1]

  A[1] = A[A.heap-size]

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

  MAX-HEAPIFY(A,1)

  return max

HEAP-INCREASE-KEY能够实现INCREASE-KEY操作,这一操作首先将对应的元素的key值改变,然后不断与其父节点比较大小,直到当前元素的关键字小于父元素关键字或者没有父元素为止。这一操作的时间复杂度是O(lgn)

HEAP-INCREASE-KEY(A,i,key)

  if key < A[i]

  error "new key is smaller than current key"

  A[i] = key

  while i > 1 and A[parent(i)] < A[i]

    exchange A[i] with A[parent(i)]

    i = parent(i)

MAX-HEAP-INSERT实现INSERT操作。首先将堆的大小加一,然后把堆增加的结点的key设为-∞,然后对这个新的节点执行INCREASE-KEY操作。MAX-HEAP-INSERT的运行时间为O(lgn)。

MAX-HEAP-INSERT(A,key)

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

  A[A.heap-size] = -∞

  HEAP-INCREASE-KEY(A,A.heap-size,key)

在一个包含n个元素的堆中,所有优先队列的操作都可以在O(lgn)时间内完成。

下面是基于最大堆的最大优先队列的C++代码:

#include<iostream>
using namespace std;
static const int inf = 999999;
class Heap{
public:
    int* arr;
    int heapSize;
    int arrSize;
    Heap(int* arr, int arrSize) :arr(arr), arrSize(arrSize), heapSize(0){}
};
int left(int i){ return 2 * i; }
int right(int i){ return 2 * i + 1; }
int parent(int i){ return i / 2; }
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);
    }
}
int heapMaximum(Heap& h) {
    return h.arr[0];
}
int heapExtractMax(Heap& h) {
    if (h.heapSize < 1) {
        cout << "heap underflow" << endl;
        return -1;
    }
    int max = h.arr[0];
    h.arr[0] = h.arr[h.heapSize - 1];
    h.heapSize--;
    maxHeapify(h, 0);
    return max;
}
void heapIncreaseKey(Heap& h, int i, int key) {
    if (key < h.arr[i]) {
        cout << "new key is smaller than current key" << endl;
        return;
    }
    h.arr[i] = key;
    while (i>0 && h.arr[parent(i)] < h.arr[i]) {
        swap(h.arr[i], h.arr[parent(i)]);
        i = parent(i);
    }
}
void maxHeapInsert(Heap& h, int key) {
    h.heapSize++;
    h.arr[h.heapSize - 1] = -inf;
    heapIncreaseKey(h, h.heapSize - 1, key);
}
int main() {
    int arr[1000];
    Heap h(arr, 1000);
    cout << "请输入10个权值:" << endl;
    int key = 0;
    for (int i = 0; i < 10; i++) {
        cin >> key;
        maxHeapInsert(h, key);
    }
    int max = heapExtractMax(h);
    cout << "最大的是:" << max << endl;
    max = heapExtractMax(h);
    cout << "第二大的是:" << max << endl;
    return 0;
}

程序执行结果: