C++实现的大顶堆:重新表达原标题
最编程
2024-08-14 20:37:44
...
【大顶堆的性质】
大顶堆是一棵完全二叉树,且树中的每个节点的值都不小于它的孩子节点的值。我们可以用一个heap数组来表示它。
【大顶堆的插入、删除】
- 大顶堆的插入:首先初始化插入位置为最后,然后从下往上调整堆(调整插入元素的位置)。在调整过程中,若当前节点的父亲节点小于插入元素,则将其父亲节点的值赋给当前节点,父亲节点作为当前节点,依此继续;否则当前节点即为插入位置。
- 大顶堆的删除:删除根,初始化最后一个元素为新根的值,然后从上往下进行调整堆(调整最后一个元素的位置)。在调整的过程中,若最后一个元素小于当前节点的孩子节点的较大值,则将孩子节点的值赋给当前节点,将孩子节点作为当前节点,依此继续;否则当前节点即为最后一个元素的位置。
【代码实现】
// maxheap_h代码
#ifndef maxheap_h
#define maxheap_h
template<class T>
class Maxheap
{
public:
Maxheap(int size);
~Maxheap();
bool Isempty();
void push(T item); //插入操作
void pop(); //删除操作
T top();
private:
T *heap;
上一篇: C语言实现大顶堆:策略和代码解析