(堆) 优先队列(堆)的简单实现
🏔️堆是什么？
堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。
每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。
优先队列 std::priority_queue 是一种 堆，一般为 二叉堆。
本文以 1845. 座位预约管理系统 为例进行使用和简单实现的讲解。(本题是小顶堆)
🏔️C++ 标准库
std::priority_queue - cppreference.com
class SeatManager {
std::priority_queue<int, vector<int>, greater<int>> heap;
public:
SeatManager(int n) {
for (int i = 1; i <= n; i += 1) {
heap.push(i);
}
}
int reserve() {
int ret = heap.top();
heap.pop();
return ret;
}
void unreserve(int seatNumber) {
heap.push(seatNumber);
}
};
class SeatManager {
vector<int> heap;
public:
SeatManager(int n) {
for (int i = 1; i <= n; ++i) {
heap.push_back(i);
}
}
int reserve() {
pop_heap(heap.begin(), heap.end(), greater<int>());
int tmp = heap.back();
heap.pop_back();
return tmp;
}
void unreserve(int seatNumber) {
heap.push_back(seatNumber);
push_heap(heap.begin(), heap.end(), greater<int>());
}
};
🏔️手动实现
⛰️原理简介
核心：用数组模拟完全二叉树。
用数组模拟完全二叉树，下标[0, n - 1]，节点i的所有子树为left = i * 2 + 1，right = i * 2 + 2。
两个重要操作，注意不要越界。
堆调整
针对我们要维护的节点fa，对其左右子节left, right点进行比较，找出最值。交换到当前节点fa上。
然后交换后的位置也要同样的维护，因此可以进行迭代或者递归。
// [0, n - 1]
int fa;
int left = (fa << 1) + 1;
int right = (fa << 1) + 2;
// e.g.
// fa = 0left = 1right = 2
尾部新元素维护
因为我们是数组模拟，不是链式的二叉树。因此直接在末尾添加元素比较方便。
而末尾的新元素要和其父元素进行比较。如果要提升，则将父元素复制到子节点。
同理不断直到根部的迭代或则递归。
// [0, n - 1]
int leaf;
int fa = (leaf - 1) / 2;
// e.g.
// leaf = 7fa = 3
// leaf = 8fa = 3
⛰️C++
座位预约管理系统 - 提交记录 - 力扣（LeetCode）
namespace lotus {
template <typename T, typename Compare = std::less<T>>
struct Heap {
public: // Member types
using value_compare = Compare;
using value_type = T;
using size_type = std::size_t;
private: // Member
std::vector<value_type> heap;
value_compare cmp;
public: // constructor & distructor
Heap() = default;
~Heap() = default;
public: // Element access
value_type& top() {
return heap[0];
}
public: // Capacity
bool empty() const {
return heap.empty();
}
size_type size() const {
return heap.size();
}
public: // Modifiers
void push(const value_type& value) {
heap.push_back(value);
// 自底向上进行调整
int i = this->size() - 1;
for (; i > 0 && cmp(value, heap[(i - 1) >> 1]); i = (i - 1) >> 1) {
heap[i] = heap[(i - 1) >> 1];
}
heap[i] = value;
}
void pop() {
value_type ret = heap.front();
heap.front() = heap.back();
heap.pop_back();
if (this->size()) {
heapify(heap, 0, this->size() - 1);
}
}
public:
static void heapify(vector<int>& arr, int fa, int border) {
assert(fa <= border);
assert((int)arr.size() - 1 <= border);
value_compare cmp{};
while ((fa << 1) + 1 <= border) {
int left = (fa << 1) + 1;
int right = (fa << 1) + 2;
int idx = fa;
if (left <= border && cmp(arr[left], arr[idx])) {
idx = left;
}
if (right <= border && cmp(arr[right], arr[idx])) {
idx = right;
}
if (idx != fa) {
swap(arr[fa], arr[idx]);
fa = idx;
} else {
break;
}
} // while loop
}
};
} // namespace lotus
class SeatManager {
lotus::Heap<int> heap;
// std::priority_queue<int, vector<int>, greater<int>> heap;
public:
SeatManager(int n) {
for (int i = 1; i <= n; i += 1) {
heap.push(i);
}
}
int reserve() {
int ret = heap.top();
heap.pop();
return ret;
}
void unreserve(int seatNumber) {
heap.push(seatNumber);
}
};
/**
* Your SeatManager object will be instantiated and called as such:
* SeatManager* obj = new SeatManager(n);
* int param_1 = obj->reserve();
* obj->unreserve(seatNumber);
*/
⛰️C语言
座位预约管理系统 - 提交记录 - 力扣（LeetCode）
// [lotus - heap - begin]
typedef size_t size_type;
typedef int value_type;
typedef bool (*value_compare)(const value_type*, const value_type*);
#define M (100000 + 10)
bool less(const void* x, const void* y) {
return *(value_type*)x < *(value_type*)y;
}
void swap(value_type* x, value_type* y) {
value_type tmp = *x;
*x = *y;
*y = tmp;
}
void heapify(value_type* arr, int fa, int border, value_compare cmp) {
assert(fa <= border);
while ((fa << 1) + 1 <= border) {
int left = (fa << 1) + 1;
int right = (fa << 1) + 2;
int idx = fa;
if (left <= border && cmp(&arr[left], &arr[idx])) {
idx = left;
}
if (right <= border && cmp(&arr[right], &arr[idx])) {
idx = right;
}
if (idx != fa) {
swap(&arr[fa], &arr[idx]);
fa = idx;
} else {
break;
}
} // while loop
}
// data struct
typedef struct {
size_type size;
value_type heap[M];
value_compare cmp;
} Heap;
// constructor & distructor
void heap_constructor(Heap* p) {
p->size = 0;
p->cmp = (value_compare)&less;
}
void heap_distructor(Heap* p) {
free(p);
}
// Element access
value_type heap_top(Heap* p) {
return p->heap[0];
}
// Capacity
bool empty(Heap* p) {
return 0 == p->size;
}
size_type size(Heap* p) {
return p->size;
}
// Modifiers
void heap_push(Heap* p, const value_type value) {
p->heap[p->size] = value;
p->size += 1;
// 自底向上进行调整
int i = p->size - 1;
for (; i > 0 && p->cmp(&value, &p->heap[(i - 1) >> 1]); i = (i - 1) >> 1) {
p->heap[i] = p->heap[(i - 1) >> 1];
}
p->heap[i] = value;
}
void heap_pop(Heap* p) {
value_type ret = p->heap[0];
p->heap[0] = p->heap[p->size - 1];
p->size += -1;
if (p->size) {
heapify(p->heap, 0, p->size - 1, p->cmp);
}
}
// [lotus - heap - end]
// [leetcode - Solution - begin]
typedef struct {
Heap* heap;
} SeatManager;
SeatManager* seatManagerCreate(int n) {
SeatManager* p = (SeatManager*)malloc(sizeof(SeatManager));
p->heap = (Heap*)malloc(sizeof(Heap));
heap_constructor(p->heap);
for (int i = 1; i <= n; i += 1) {
heap_push(p->heap, i);
}
return p;
}
int seatManagerReserve(SeatManager* obj) {
int ret = heap_top(obj->heap);
heap_pop(obj->heap);
return ret;
}
void seatManagerUnreserve(SeatManager* obj, int seatNumber) {
heap_push(obj->heap, seatNumber);
}
void seatManagerFree(SeatManager* obj) {
heap_distructor(obj->heap);
free(obj);
}
// [leetcode - Solution - end]
/**
* Your SeatManager struct will be instantiated and called as such:
* SeatManager* obj = seatManagerCreate(n);
* int param_1 = seatManagerReserve(obj);
* seatManagerUnreserve(obj, seatNumber);
* seatManagerFree(obj);
*/
⭐END
🌟交流方式
关注我，学习更多C/C++，python，算法，软件工程，计算机知识！
B站
👨💻主页：天赐细莲 bilibili
原文地址：https://blog.csdn.net/CUBE_lotus/article/details/144411939
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！