堆---实现最小堆及堆的插入与删除

堆

---

堆在优先级队列的各种实现中，是最高效的一种数据结构
假定在各个数据记录（或元素）中存在一个能够标识数据记录（或元素）的数据项，并将依据该数据项对数据进行组织，则可数据项成为关键码（key）
如果有一个关键码的集合K = {k0 , k1 , k2 , … , kn-1},把它的所有元素按完全二叉树的顺序存储存放在一个一维数组中。并且满足：

ki <= k2i+1 且 ki <= k2i+2 或者（ki >= k2i+1 且 ki >= k2i+2）i = 0 , 1 , … , [(n - 2) / 2]
则称这个集合为最小堆（或最大堆）

由于堆存储在下标从0开始计数的数组中，因此，在堆中给定下标为i的结点时：

1. 如果 i = 0，结点 i 是根结点，无父结点；否则结点 i 的父结点为结点 [(i - 2) / 2]
2. 如果 2i + 1 > n - 1，则结点 i 无左子女；否则结点 i 的左子女为结点 2i + 1
3. 如果 2i + 2 > n - 1，则结点 i 无右结点；否则结点 i 的右子女为结点 2i + 2

实现最小堆

第一步：建堆
利用给定的数组大小和数组元素，创建堆空间，并进行拷贝。
第二步：调整成为最小堆
利用自定义的siftDown()函数，实现下滑调整。

插入与删除

插入

删除
由于堆是队列结构，只能从堆中删除堆顶元素。移除堆顶元素之后，用堆的最后一个节点填补取走的堆顶元素，并将堆的实际元素个数减1。但用最后一个元素取代堆顶元素之后有可能破坏堆，因此需要将对自顶向下调整，使其满足最大或最小堆。

代码实现

#include<iostream>
using namespace std;


template<class T>
class Heap
{
public:
    //构造函数
    Heap()
    :haep(NULL)
    {}

    //构造函数
    Heap(T * arr, int sz)
    {
        HeapSize = (DefaultSize < sz) ? sz : DefaultSize;
        heap = new T[HeapSize];
        heap = arr;
        if (heap == NULL)
            cout << "内存分配失败！" << endl;
        for (int i = 0; i < sz; i++)
            heap[i] = arr[i];
        currentSize = sz;
    }

    //调整为小堆
    void MinHeap()
    {
        currentPos = (currentSize - 2) / 2;//最初调整位置：最后分支点
        while (currentPos >= 0)
        {
            siftDown(currentPos, currentSize-1);
            currentPos--;
        }

    }

    //向堆插入新元素
    bool Insert(T x)
    {
        if (currentSize == HeapSize)
        {
            cerr << "Heap Full" << endl;
            return false;
        }

        heap[currentSize] = x;
        siftUp(currentSize);
        currentSize++;
        return true;

    }

private:
    T * heap;//存放堆的数组
    int DefaultSize = 10;//默认堆的大小
    int HeapSize;//当前堆的大小
    int currentSize;//最小堆中当前元素个数
    int currentPos;//最初调整位置

    //从start到m下滑调整成为最小堆
    void siftDown(int start, int m)
    {
        int i = start;
        int j = 2 * i + 1;
        T temp = heap[i];
        while (j <= m)
        {
            if (j < m && heap[j] > heap[j + 1])
                j = j + 1;

            if (temp <= heap[j])
                break;
            else
            {
                heap[i] = heap[j];
                i = j;
                j = 2 * j + 1;
            }   
        }
        heap[i] = temp;
    }

    //从start到0上滑调整成为最小堆
    void siftUp(int start)
    {
        int j = start;
        int i = (start - 1) / 2;
        T temp = heap[j];
        while (j > 0)
        {           
            if (heap[i] >= temp)
            {
                heap[j] = heap[i];
                j = i;
                i = (i - 1) / 2;
            }
        }
        heap[j] = temp;
    }
};



int main()
{
    int arr[6] = { 5, 4, 3, 2, 1, 0 };
    Heap<int> s(arr, 6);
    s.MinHeap();
    s.Insert(-1);
    for (int i = 0; i < 6; i++)
        cout << arr[i] << " ";
    return 0;


}