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);
}
}
}
