堆的一般操作 (大顶堆同理)

  • build:建立一个空堆(这里为构造函数)
  • insert:向堆中插入一个新元素
  • update:将新元素提升使其符合堆的性质
  • getTop:获取当前堆顶元素的值
  • heapify:使删除堆顶元素的堆再次成为堆
#include <iostream>

using namespace std;


/*
*   @minHeap    用数组arr 创建一个堆
*   @update     把pos位置上的元素放到合适位置
*   @print      打印(测试用)
*   @getTop     获得堆顶元素
*   @heapify    删除堆顶元素并返回 其余元素仍是堆
*   @~minHeap   释放内存
*/
class minHeap
{
private:
    int *arr;
    int siz;

public:
    minHeap(int arr[], int n);
    void insert_(int data);
    void update(int pos);
    void print();
    int getTop();
    int heapify();
    ~minHeap();
};


int main()
{
    int arr[5] = {5, 8, 9, 4, 3};
    minHeap hp(arr, 5);
    hp.print();
    hp.insert_(2);
    hp.print();
    hp.heapify();
    hp.print();
    return 0;
}


minHeap::minHeap(int arr[], int n)
{
    this->arr = new int[10005];
    for(int i(0); i<n; i++)
    {
        this->arr[i] = arr[i];
    }
    siz = n;

    //不断维护每个节点
    for(int i = siz/2; i>=0; i--)
        update(i);
}

void minHeap::update(int pos)
{
    int least;//最小值的坐标 不是最小值
    do
    {
        int l = pos*2 + 1;//左孩子
        int r = pos*2 + 2;//右孩子
        //具体为什么 自己画一颗树就知道了 (根为1)

        //当左孩子在节点范围内 且 左孩子小于他的父亲时, 更新最小值的坐标
        if(l < siz && arr[l] < arr[pos])
        {
            least = l;
        }
        else
        {
            least = pos;
        }

        //当其右孩子在节点内, 且右孩子更小 更新最小值的坐标
        if(r < siz && arr[r] < arr[least])
        {
            least = r;
        }

        //当最小值是其本身时 停止更新
        if(least == pos)
        {
            break;
        }
        //否则应与最小值交换 继续向下维护
        else
        {
            swap(arr[pos], arr[least]);
            pos = least;
        }

    }
    while(least < siz);
}

int minHeap::getTop()
{
    return arr[0];
}

/*
思路:
把新元素加到最后, 不断与其父亲比较,直到新元素找到合适位置
*/
void minHeap::insert_(int data)
{
    arr[siz] = data;
    int pos = siz++;
    do
    {
        int p = (pos-1)/2;
        if(arr[p] > arr[pos])
        {
            swap(arr[p], arr[pos]);
            pos = p;
        }
        else
            break;
    }
    while(pos > 0);
}

void minHeap::print()
{
    for(int i(0); i<siz; i++)
    {
        if(i < siz-1)
            cout << arr[i] << ' ';
        else
            cout << arr[i] << endl;
    }
}
//返回堆顶素,将最后的元素放到堆顶,然后维护
int minHeap::heapify()
{
    int tmp = arr[0];
    arr[0] = arr[--siz];
    update(0);
    return tmp;
}

minHeap::~minHeap()
{
    delete[] arr;
}

运行结果