堆

在优先级队列的各种实现中，堆是最高效的一种数据结构。

类定义

最小堆的类定义。

\#define DefaultSize 10;
enum bool {false, true}
template <class T, class E>
class MinHeap: public MinPQ<T,E> {
public:
    MinHeap(int sz = DefaultSize);
    MinHeap(E arr[], int n);
    ~MinHeap() {delete []heap;}
    bool Insert(const E& x);
    bool RemoveMin(E& x);
    bool IsEmpty() const {
        return (currentSize == 0) ? true: false;
    }
    bool IsFull() const {
        return (currentSize == maxHeapSize) ? true : false;
    }
    void MakeEmpty() {currentSize = 0;}
    
private:
    E *heap;
    int currentSize;
    int maxHeapSize;
    void siftDown(int start, int m);
    void siftUp(int start);
};

构造函数

两种方式。

template<class T, class E>
MinHeap<T>::MinHeap(int maxHeapSize) {
    maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize;
    heap = new E[maxHeapSize];
    if (heap == NULL) {
        cerr << "Allocation Error" << endl;
        exit(1);
    }
    currentSize = 0;
};

template <class T, class E>
MinHeap<T>::MinHeap(E arr[], int n) {
    maxHeapSize = (DefaultSize < n) ? n : DefaultSize;
    heap = new E[maxHeapSize];
    if (heap == NULL) {
        cerr << "Allocation Error" << endl;
        exit(1);
    }
    for (int i = 0; i < n; i ++) {
        heap[i] = arr[i];
    }
    currentSize = n;
    int currentPos = (currentSize - 2) / 2;
    while (currentPos >= 0) {
        siftDown(currentPos, currentSize - 1);
        currentPos --;
    }
};

下滑调整算法。

template <class T, class E>
void MinHeap<T>::siftDown(int start, int m) {
    int i = start, j = 2 * i + 1;
    E temp = heap[i];
    while (j <= m) {
        if (j < m && heap[j] > heap[j + 1]) {
            j ++;
        }
        if (temp <= heap[j]) {
            break;
        } else {
            heap[i] = heap[j];
            i = j;
            j = 2 * j + 1;
        }
    }
    heap[i] = temp;
};

上滑调整算法。

template <class T, class E>
void MinHeap<T>::FilterUp(int start) {
    int j = start, i = (j-1)/2;
    E temp = heap[j];
    while (j > 0) {
        if (heap[i] <= temp) {
            break;
        } else {
            heap[j] = heap[i];
            j = i;
            i = (i-1)/2;
        }
    }
    heap[j] = temp;
};

插入。

template <class T, class E>
bool MinHeap<T>::Insert(const E& x) {
    if (currentSize == maxHeapSize) {
        cerr << "Heap Full" << endl;
        return false;
    }
    heap[currentSize] = x;
    siftUp(currentSize);
    currentSize ++;
    return true;
};

删除。

template <class T, class E>
bool MinHeap<T>::RemoveMin(E& x) {
    if (!currentSize) {
        cout << "Heap empty" << endl;
        return false;
    }
    x = heap[0];
    heap[0] = heap[currentSize - 1];
    currentSize --;
    siftDown(0, currentSize-1);
    return true;
};