欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

C++实现的大顶堆:重新表达原标题

最编程 2024-08-14 20:37:44
...

【大顶堆的性质】

大顶堆是一棵完全二叉树,且树中的每个节点的值都不小于它的孩子节点的值。我们可以用一个heap数组来表示它。

【大顶堆的插入、删除】

  1. 大顶堆的插入:首先初始化插入位置为最后,然后从下往上调整堆(调整插入元素的位置)。在调整过程中,若当前节点的父亲节点小于插入元素,则将其父亲节点的值赋给当前节点,父亲节点作为当前节点,依此继续;否则当前节点即为插入位置。
  2. 大顶堆的删除:删除根,初始化最后一个元素为新根的值,然后从上往下进行调整堆(调整最后一个元素的位置)。在调整的过程中,若最后一个元素小于当前节点的孩子节点的较大值,则将孩子节点的值赋给当前节点,将孩子节点作为当前节点,依此继续;否则当前节点即为最后一个元素的位置。

【代码实现】

// 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;