数据结构——堆的基本操作（堆的建立、插入、删除等）详解

绝地灬酷狼 2023-03-01 05:36 14阅读 0赞

## 前言 ##

[数据结构之——堆（Heap）][Heap]  
此篇博客粗略讲解了堆的一些概念  
接下来讲解堆的一些基本操作  
本次堆的操作均以最大堆（大顶堆）为例

## 堆的建立 ##

#define MAXDATA 10000
    struct HNode {
        
        int* Data;         			   // 存储元素的数组 
        int Size;          			   // 堆中当前元素个数 
        int Capacity;      			   // 堆的最大容量 
    };
    // 创建容量为MaxSize的空的最大堆 
    HNode* CreateHeap(int MaxSize) {
        
        HNode* H = new HNode;
        H->Data = new int[MaxSize + 1];//此处堆数据的存放从下标为1开始
        H->Size = 0;
        H->Capacity = MaxSize;
        H->Data[0] = MAXDATA;          //定义"哨兵"为大于堆中所有可能元素的值,例如定义哨兵为10000
        return H;
    }

## 判断堆空满 ##

bool IsFull(HNode* H)
    {
        
        return (H->Size == H->Capacity);
    }
    bool IsEmpty(HNode* H)
    {
        
        return (H->Size == 0);
    }

## 堆的插入 ##

思路：

1.  插入前先判断堆是否已满，若不满，则先插入到叶节点上
2.  判断此时的堆的逻辑结构是否正确，不正确则调整至正确为止

HNode* Insert(HNode* H, int key) {
        
        if (IsFull(H)) {
        
            cout << "The heap is full\n";    //输出堆满提示
            return H;                        //返回根节点
        }
        int i = ++H->Size;                   //为堆的Size增加1，同时使i指向堆的最后一个位置，
        for (; H->Data[i / 2] < key; i /= 2) //通过循环找到 key 应该插入的位置
                H->Data[i] = H->Data[i / 2]; //上滤 key
        H->Data[i] = key;                    //插入 key
        return H;                            //返回根节点
    }

## 删除最大堆顶元素 ##

堆是一种特殊的“队列”，取出元素的顺序依照元素的优先权（关键字）大小，所以删除操作其实是删除根节点  
思路：

1.  根节点删除后，我们会有两个子树，我们需要基于它们重构堆。
2.  先让最后一个节点成为新的跟节点，从而构成一个新的二叉树。
3.  再将新的根节点不断的和子节点比较。如果新的跟节点比两个子节点中大的那一个小，则和该子节点交换。直到该节点不小于任一子节点，或者其成为叶节点。

int DeleteMax(HNode* H)
    {
        
        int Parent, Child;
        int MaxItem, X;
    
        if (IsEmpty(H)) {
        
            cout << "The heap is empty\n";                                  //提示堆已空
            return -1;                                                      //返回错误提示
        }
    
        MaxItem = H->Data[1];                                               //取出根结点存放的最大值 
        X = H->Data[H->Size--];                                             //X存贮最后一个节点的值，并将Size减少
        for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        
            Child = Parent * 2;
            if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
                Child++;                                                    // Child指向左右子结点的较大者 
            if (X >= H->Data[Child]) break;                                 // 找到了X的位置
            else                                                            // 下滤X 
                H->Data[Parent] = H->Data[Child];
        }
        H->Data[Parent] = X;
    
        return MaxItem;
    }

Ps:若有错误，欢迎指出

[Heap]: https://blog.csdn.net/leowahaha/article/details/107469770