Learning to be Giant.

Binary Heap 实现笔记

|

说实话,作为一个程序员,对于一些基本算法竟然只停留在了理解层面上儿从来没曾实践过实在是可笑。为了弥补自己的这个问题,从今天开始我打算把一些常用的算法都实现一下,在实践当中进一步加深理解。

堆在计算机当中常被使用,特别是在排序和优先队列的视线当中。今天我自己实现了一下比较简单的二叉堆。

构造堆的时间复杂度为$O(n)$,插入和删除操作的复杂度为$O(logn)$,堆排序的时间复杂度为$O(nlogn)$。复杂度的推导可见网上的其他文章。

这里给出我的实现:

class MaxHeap {
private:
    vector<int> entries;
    void heapify();
    void shiftDown(size_t idx);
    void shiftUp(size_t idx);
public:
    MaxHeap() = default;
    MaxHeap(vector<int> const& rhs);
    void removeWithIndex(size_t idx);
    void remove(int key);
    int max();
    void popMax();
    void add(int key);
    size_t size() {
        return entries.size();
    }
};

void MaxHeap::heapify() {
    if (entries.size() < 2) return;
    size_t start_idx = (size_t)(entries.size() / 2) - 1;
    for (size_t idx = start_idx; idx != 0; idx--) {
        shiftDown(idx);
    }
    shiftDown(0); // make up for the for condidition
}

void MaxHeap::shiftDown(size_t idx) {
    size_t change_idx = -1;
    if (idx * 2 + 2 < entries.size()) {
        int tmp = 0;
        if (entries[idx*2+1] > entries[idx*2+2]) {
            change_idx = idx*2+1;
            tmp = entries[idx*2+1];
        } else if (entries[idx*2+1] < entries[idx*2+2]) {
            change_idx = idx*2+2;
            tmp = entries[idx*2+2];
        }
        if (tmp > entries[idx]) {
            swap(entries[idx], entries[change_idx]);
            shiftDown(change_idx);
        }
    } else if (idx * 2 + 1 < entries.size()) {
        if (entries[idx] < entries[idx*2+1]) {
            swap(entries[idx], entries[idx*2+1]);
        }
    }
}

MaxHeap::MaxHeap(vector<int> const& rhs) {
    entries = rhs;
    heapify();
}

void MaxHeap::removeWithIndex(size_t idx) {
    entries[idx] = entries.back();
    entries.pop_back();
    shiftDown(idx);
}

void MaxHeap::remove(int key) {
    for (size_t idx = 0; idx < entries.size(); idx++) {
        if (entries[idx] == key) {
            removeWithIndex(idx);
            return;
        }
    }
}

int MaxHeap::max() {
    return entries[0];
}

void MaxHeap::popMax() {
    removeWithIndex(0);
}

void MaxHeap::shiftUp(size_t idx) {
    if (idx == 0) return;
    int parent_idx = (int)((idx - 1)/2);
    if (entries[parent_idx] < entries[idx]) {
        swap(entries[parent_idx], entries[idx]);
        shiftUp(parent_idx);
    }
}

void MaxHeap::add(int key) {
    entries.push_back(key);
    shiftUp(entries.size() - 1);
}

堆的实现比较简单,我在这次实现当中着重注意了复用和面向对象。此次实现过程当中唯一值得说明的一点就是C++当中的size_t这个类型事实上是一个与机器相关的unsigned的类型,在64位系统当中为unsigned long。这就是为什么我在上面有一行当中注释说要make up什么的,因为我如果直接判断idx >= 0这个循环就变成死循环了。

Comments