数据结构-堆

堆（Heap）是一种特别的树状数据结构。

若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。

若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。

在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。

堆排序（heap sort），提出了二叉堆树作为此算法的数据结构。

在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

• 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
• 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

支持的基本操作

例程

为将元素X插入堆中，找到空闲位置，创建一个空穴，若满足堆序性（heap order），则插入完成；否则将父节点元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做上滤（percolate up）

//插入到一个二叉堆的过程
void Insert( ElementType X, PriorityQueue H ) 
{
    int i;
    
    if (IsFull(H)) 
    {
        printf("Queue is full.\n");
        return;
    }
    for (i = ++H->Size; H->Element[i / 2] > X; i /= 2)
        H->Elements[i] = H->Elements[i / 2];
    H->Elements[i] = X;
}

DeleteMin，删除最小元，即二叉树的根或父节点。删除该节点元素后，队列最后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。

ElementType DeleteMin(PriorityQueue H) 
{
    int i, Child;
    ElementType MinElement, LastElement;
    if (IsEmpty(H)) 
    {
        printf("Queue is empty.\n");
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];
    for (i = 1; i * 2 <= H->Size; i = Child) 
    {
        // Find smaller child.
        Child = i * 2;
        if ( (Child != H->Size) && (H->Elements[Child + 1] <  H->Elements[Child]) )
            Child++;
        // Percolate one level.
        if (LastElement > H->Elements[Child])
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

c++实现

#pragma once
template<class T>

class JBMinHeap
{
private:
    //申请堆空间
    T *_minHeap = NULL;
    int _index,_maxSize;
public:
    JBMinHeap(int maxSize) 
    {
        _maxSize = maxSize;
        _minHeap = new T[_maxSize];
        _index = -1;
    }
    JBMinHeap(JBMinHeap &h) 
    {
        _index = h._index;
        _maxSize = h._maxSize;
        _minHeap = new T[_maxSize];
        for (int i = 0;i<_maxSize) 
        {
            *_minHeap[i] = *h._minHeap[i];
        }
    }
    ~JBMinHeap() 
    {
        delete[]_minHeap;
    }
    //获取整个最小堆的头部指针
    T * getMinHeap() 
    {
        return _minHeap;
    }
    //判断堆是不是空的
    bool isEmpty() 
    {
        return _index == -1;
    }
    bool add(T x) 
    {
        if (isFull()) 
        {
            return false;
        }
        _index++;
        _minHeap[_index] = x;
        return true;
    }
    bool isFull() 
    {
        return _index == _maxSize;
    }
    //堆进行向下调整
    void adjustDown(int index);
    //队进行向上调整
    void adjustUp(int index);
    //建堆运算
    void createMinHeap() 
    {
        if (isEmpty()) 
        {
            return;
        }
        for (int i = (_index-1)/2;i >-1;i--) 
        {//直接从倒数第二层 逐层向下调整
            adjustDown(i);
        }
    }
};

template<class T>
void JBMinHeap<T>::adjustDown(int index) 
{
    if (isEmpty()) 
    {
        return;
    }
    while (index<_index)
    {
        T temp = _minHeap[index];//将当前索引的位置的值保存下来
        int oneC = 2 * index + 1;//获取到两个孩子的位置
        int twoC = 2 * index + 2;
        
        if (oneC == _index) 
        {//若第一个孩子是整个堆最后一个位置 则直接执行交换操作并结束执行
                _minHeap[index] = _minHeap[oneC];
                _minHeap[oneC] = temp;
                return;
        }
        if (twoC >_index) 
        {//如果第二个孩子的索引位置越界 结束执行
            return;
        }
        if (_minHeap[oneC] <= _minHeap[twoC]) 
        {//正常情况的数据交互执行
            if (temp > _minHeap[oneC]) 
            {
                _minHeap[index] = _minHeap[oneC];
                _minHeap[oneC] = temp;
                index = oneC;
            }
            else {//如果该处索引值已经是比两个孩子小 则结束循环
                index = _index;
            }
        }
        else 
        {
            if (temp > _minHeap[twoC]) 
            {
                _minHeap[index] = _minHeap[twoC];
                _minHeap[twoC] = temp;
                index = twoC;
            }
            else 
            {
                index = _index;
            }
        }
    }
}

template<class T>
void JBMinHeap<T>::adjustUp(int index) 
{
    if (index > _index) 
    {//大于堆的最大值直接return
        return;
    }
    while (index>-1)
    {
        T temp = _minHeap[index];
        int father = (index - 1) / 2;
        if (father >= 0) 
        {//如果索引没有出界就执行想要的操作
            if (temp < _minHeap[father]) 
            {
                _minHeap[index] = _minHeap[father];
                _minHeap[father] = temp;
                index=father;
            }
            else 
            {//若果已经是比父亲大 则直接结束循环
                index = -1;
            }
        }
        else//出界就结束循环
        {
            index = -1;
        }
    }
}