堆和优先队列 Heap and Priority Queue

什么是优先队列？

普通的队列: 先进先出；后进后出。

优先队列: 出队顺序和入队顺序无关，和优先级相关。

优先队列这种概念在计算机科学中被大量使用，最典型的应用情况，在操作系统中执行任务。操作系统要同时执行多个任务，可是实际上，操作系统是将CPU的执行周期划分成时间片，在每个时间片里只能执行一个任务。那么究竟要执行哪个任务呢？答案就是每一个任务都有一个优先级，操作系统将动态的每一次选择优先级最高的任务进行执行，我们要想动态选择优先级最高的任务执行，就需要使用优先队列。也就是说操作系统的所有任务都进入优先队列，由优先队列来调度每次需要执行的任务。

关键词： 动态

如果我们的任务永远是固定的话，那么我们完全可以把这些任务排一次序，然后从优先级最高到优先级最低依次执行。可是实际上，当我们使用优先队列的时候，情况通常都非常复杂。

当我们选择执行某一个请求之后，下一步可能不是简单的去执行其他的请求。因为，与此同时，也有可能又来了很多新的任务。当然，真正的操作系统情况会更加复杂。一旦来了新的任务，旧的任务的优先级本身也有可能会改变。因此，在这种情况下，一次性的将所有任务进行排序，然后依次执行是不现实的。如果使用这样的排序的方式来解决问题的话，那么很有可能是每一次运行完了某一个任务之后，都要再堆剩下的任务进行一次新的排序。然而，我们这样做的耗时将是巨大的。

为什么要使用优先队列？

在 1000000 个元素中选出前 100 名？在 N 个元素中选出前 M 个元素。

排序？ NlogN

使用优先队列: NlogM 快十几倍

优先队列主要操作

• 入队
• 出队（取出优先级最高的的元素）

优先队列的实现

对于总共 N 个请求：

使用普通数组或者顺序数组，最差情况：$O(n^2)$

使用堆: $O(nlogn)$

堆的基本实现

二叉堆 Binary Heap

二叉堆是一棵完全二叉树：堆中某个节点的值总是不大于其父节点的值；堆总是一课完全二叉树。最大堆。

用数组存储二叉堆

#include<iostream>
#include<algorithm>
#include<string>
#include<ctime>
#include<cmath>
#include<cassert>
using namespace std;

template<typename Item>
class MaxHeap {
public:
    MaxHeap(int capacity) {
        data = new Item[capacity + 1];
        count = 0;
    }

    ~MaxHeap(){
        delete [] data;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

private:
    Item* data;
    int count;
};

int main(){
    MaxHeap<int> maxheap = MaxHeap<int>(100);
    cout << maxheap.size() << endl;
    return 0;
}

Shift Up

#include<iostream>
#include<algorithm>
#include<string>
#include<ctime>
#include<cmath>
#include<cassert>
using namespace std;

template<typename Item>
class MaxHeap {
public:
    MaxHeap(int capacity) {
        data = new Item[capacity + 1];
        count = 0;
        this->capacity = capacity;
    }

    ~MaxHeap(){
        delete [] data;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

    void insert(Item item) {
        assert(count+1 <= capacity);
        data[count+1] = item;
        count++;
        shiftUp(count);
    }

private:
    Item* data;
    int count;
    int capacity;

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

int main(){
    MaxHeap<int> maxheap = MaxHeap<int>(100);
    cout << maxheap.size() << endl;

    srand(time(NULL));
    for(int i = 0; i < 15; i++) {
        maxheap.insert(rand() % 100);
    }

    cout << maxheap.size() << endl;

    return 0;
}

Shift Down

#include<iostream>
#include<algorithm>
#include<string>
#include<ctime>
#include<cmath>
#include<cassert>
using namespace std;

template<typename Item>
class MaxHeap {
public:
    MaxHeap(int capacity) {
        data = new Item[capacity + 1];
        count = 0;
        this->capacity = capacity;
    }

    ~MaxHeap(){
        delete [] data;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

    void insert(Item item) {
        assert(count+1 <= capacity);
        data[count+1] = item;
        count++;
        shiftUp(count);
    }

    Item extractMax() {
        assert(!isEmpty());
        Item ret = data[1];
        swap(data[1], data[count]);
        count--;
        shiftDown(1);
        return ret;
    }

private:
    Item* data;
    int count;
    int capacity;

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

    void shiftDown(int k) {
        while(2 * k <= count) {
            int j = 2 * k;  // 在此轮循环中， data[k] 和 data[j] 交换位置
            if(j+1 <= count && data[j+1] > data[j]) j += 1;
            if(data[k] >= data[j]) break;
            swap(data[k], data[j]);
            k = j;
        }
    }
};

int main(){
    MaxHeap<int> maxheap = MaxHeap<int>(100);
    cout << maxheap.size() << endl;

    srand(time(NULL));
    for(int i = 0; i < 15; i++) {
        maxheap.insert(rand() % 100);
    }

    while(!maxheap.isEmpty())
        cout << maxheap.extractMax() << " ";

    return 0;
}

Heapify

将 n 个元素逐个插入到一个空堆中，算法复杂度是 $O(nlogn)$

heapify 的过程，算法复杂度为 $O(n)$