堆Heap

Heap

Heap: 堆。一般也称作Priority Queue(即优先队列）

堆我们一般用一个二叉树来表示。即一个非叶子节点有至多2个子节点。

堆一般分为大堆和小堆。大堆的意思是，对任意一个非叶子节点，它的值大于它的子节点的值。此时，root（堆顶）的值是整棵树最大的值。小堆的意思刚好想法，对任意一个非叶子节点，它的值小于它的子节点的值。此时root的值是整棵树的最小值。

堆可以用来排序，也可以按优先级来存储数据。

c++中有std::priority_queue

下面是我自己的一个简单实现：

// .h
#ifndef AGORITHM_PRIORITYQUEUE_H
#define AGORITHM_PRIORITYQUEUE_H


#include <cstdint>
#include <vector>
#include <functional>

class PriorityQueue {
public:
    using ValueType = int;
    using CmpFunc = std::function<bool(ValueType, ValueType)>;

    virtual ~PriorityQueue() = default;

    explicit PriorityQueue();

    explicit PriorityQueue(uint32_t initialCap);

    explicit PriorityQueue(uint32_t initialCap, const CmpFunc &func);

    virtual void Push(int value);

    virtual int Pop();

    virtual int Top() const;

    bool Empty() const;

    uint32_t Size() const;

    bool IsLeaf(uint32_t pos);

    int DeleteNodeAt(uint32_t pos);

    ValueType ValueAt(uint32_t pos);

    static const int INITIAL_CAP = 8;

    static const int FIRST_POS = 1;

protected:
    CmpFunc GetCmpFunc() const;

    static uint32_t bubbleDown(std::vector<int> &heap, uint32_t heapSize, uint32_t position, const CmpFunc &cmpFunc);

    static int bubbleUp(std::vector<int> &heap, uint32_t root, uint32_t heapSize, uint32_t position,
                        const CmpFunc &cmpFunc);

private:
    std::vector<int> mHeap;
    CmpFunc mCmpFunc = nullptr;
    uint32_t mHeapSize = 0;
};

#endif //AGORITHM_PRIORITYQUEUE_H


// .cpp


PriorityQueue::PriorityQueue() : PriorityQueue(INITIAL_CAP, nullptr) {
}

PriorityQueue::PriorityQueue(uint32_t initialCap) : PriorityQueue(initialCap, nullptr) {
}

PriorityQueue::PriorityQueue(uint32_t initialCap, const CmpFunc &func)
        : mHeap(initialCap), mCmpFunc(func) {
    if (!mCmpFunc) {
        mCmpFunc = [](ValueType v1, ValueType v2) -> bool {
            return v1 <= v2;
        };
    }
}

void PriorityQueue::Push(int value) {
    if (mHeapSize + 1 >= mHeap.size()) {   // enlarge heap
        mHeap.resize(mHeapSize * 2);
    }
    mHeap[++mHeapSize] = value;
    bubbleUp(mHeap, FIRST_POS, mHeapSize, mHeapSize, mCmpFunc);
}

int PriorityQueue::Pop() {
    if (Empty()) {
        throw std::out_of_range("queue empty");
    }

    int value = mHeap[FIRST_POS];

    std::swap(mHeap[FIRST_POS], mHeap[mHeapSize--]);
    bubbleDown(mHeap, mHeapSize, FIRST_POS, mCmpFunc);
    return value;
}

int PriorityQueue::Top() const {
    return mHeap[FIRST_POS];
}

bool PriorityQueue::Empty() const {
    return mHeapSize == 0;
}

uint32_t PriorityQueue::bubbleDown(std::vector<int> &heap, uint32_t heapSize, uint32_t position,
                                   const CmpFunc &cmpFunc) {
    if (heapSize <= 1) {
        return heapSize;
    }

    int value = heap[position];

    uint32_t j = position;

    while (j * 2 <= heapSize) {
        uint32_t child = j * 2;
        if (child + 1 <= heapSize && cmpFunc(heap[child + 1], heap[child])) {
            child++;
        }
        if (!cmpFunc(value, heap[child])) { // value > head[child]
            std::swap(heap[j], heap[child]);
            j = child;
        } else {
            break;
        }
    }
    heap[j] = value;
    return j;
}

int PriorityQueue::bubbleUp(std::vector<int> &heap, uint32_t root, uint32_t heapSize, uint32_t position,
                            const CmpFunc &cmpFunc) {
    if (heapSize <= 1) {
        return heapSize;
    }

    int value = heap[position];

    int j = position;
    while (j / 2 >= root) {
        int parent = j / 2;
        if (cmpFunc(value, heap[parent])) {    // value < heap[parent]
            std::swap(heap[j], heap[parent]);
            j /= 2;
        } else {
            break;
        }
    }
    heap[j] = value;

    return j;
}

uint32_t PriorityQueue::Size() const {
    return mHeapSize;
}

bool PriorityQueue::IsLeaf(uint32_t pos) {
    return (pos * 2) > Size();
}

int PriorityQueue::DeleteNodeAt(uint32_t pos) {
    if (pos > Size() || pos == 0) {
        throw std::out_of_range("HeapSize: " + std::to_string(mHeapSize) + ", pos: " + std::to_string(pos));
    }

    if (pos == Size()) {
        mHeapSize--;
        return mHeap[pos];
    }

    int value = mHeap[pos];

    mHeap[pos] = mHeap[mHeapSize];
    mHeapSize--;

    bubbleDown(mHeap, mHeapSize, pos, mCmpFunc);

    return value;
}

PriorityQueue::ValueType PriorityQueue::ValueAt(uint32_t pos) {
    if (pos > Size() || pos == 0) {
        throw std::out_of_range("HeapSize: " + std::to_string(mHeapSize) + ", pos: " + std::to_string(pos));
    }
    return mHeap[pos];
}

PriorityQueue::CmpFunc PriorityQueue::GetCmpFunc() const {
    return mCmpFunc;
}

对Heap抽象一个iterator不是现实的。

下面是一个固定大小的堆。它可以用来从一列数中找出最小的n个数。存储空间是O(1)。时间复杂度是O(n)

//.h

#ifndef AGORITHM_FIXEDSIZEPRIORITYQUEUE_H
#define AGORITHM_FIXEDSIZEPRIORITYQUEUE_H


#include "PriorityQueue.h"

// FixedPriorityQueue

// insertion time: if Size() > fixedSize: O(fixedSize) else: O(log(fixedSize))

class FixedPriorityQueue : public PriorityQueue {
public:
    explicit FixedPriorityQueue(uint32_t fixedSize);

    FixedPriorityQueue(uint32_t fixedSize, const CmpFunc &func);

    void Push(int value) override;

private:
    uint32_t mFixedSize = 0;
};


#endif //AGORITHM_FIXEDSIZEPRIORITYQUEUE_H

// .cpp
#include <iostream>
#include "FixedPriorityQueue.h"

FixedPriorityQueue::FixedPriorityQueue(uint32_t fixedSize) : FixedPriorityQueue(fixedSize, nullptr) {
}

FixedPriorityQueue::FixedPriorityQueue(uint32_t fixedSize, const PriorityQueue::CmpFunc &func)
        : PriorityQueue(fixedSize + 1, func) {
    mFixedSize = fixedSize;
}

void FixedPriorityQueue::Push(int value) {
    PriorityQueue::Push(value);

    const uint32_t N = Size();
    if (N > mFixedSize) {
        auto cmp = GetCmpFunc();
        auto minValue = ValueAt(N);
        uint32_t j = N - 1;
        uint32_t minPos = j;
        for (; j >= FIRST_POS && IsLeaf(j); j--) {  // find the minimum value
            auto curr = ValueAt(j);
            if (cmp(minValue, curr)) {
                minPos = j;
                minValue = curr;
            }
        }

        if (minPos >= FIRST_POS) {
            DeleteNodeAt(minPos);
        }
    }
}