堆

//数据结构-堆，用C++类实现，这里以小顶堆为例，所谓的堆，是一种以完全二叉树为基础的数据结构，二话不说，上代码；

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<list>

using namespace std;

class Heap
{
    size_t maxsize;
    size_t len;
    int *arr;
public:
    Heap() :maxsize(10), len(0), arr(new int[maxsize]){}
    ~Heap()
    {
        if (arr != nullptr)
        {
            delete arr;
            arr = nullptr;
            maxsize = len = 0;
        }
    }
    void insert(int data)
    {
        if (maxsize < len)//内存不足够
        {
            maxsize += (maxsize >> 1)>1 ? maxsize >> 1 : 1;
            int *temp = new int[maxsize];

            if (arr != nullptr)
            {
                memcpy(temp, arr, sizeof(int)*len);
                delete[]arr;
                arr = temp;
            }
            arr[len++] = data;
            size_t index = len - 1;//data的下标
            int mytemp;
            while (index > 0)//不是根节点
            {
                //父节点的下标   (index-1)/2
                if (arr[index] < arr[(index - 1) / 2])//父节点大于儿子
                {
                    //父节点大于儿子 交换
                    mytemp = arr[index];
                    arr[index] = arr[(index - 1) / 2];
                    arr[(index - 1) / 2] = mytemp;

                    index = (index - 1) / 2;//继续往上调整
                }
                else
                {
                    break;
                }
            }
        }
    }

    int pop()//删除
    {
        if (arr == nullptr || len == 0) throw"heap is NULL";
        int mytemp = arr[0];
        size_t index, index1, index2, temp;
        arr[0] = arr[--len];
        index = 0;
        while (index < len)
        {
            index1 = index * 2 + 1;//左孩子
            index2 = index * 2 + 2;//右孩子
            //  1.有右孩子 必定会有左孩子
            //  2.有左边未必有右孩子
            if (index1 >= len)
                break;

            else if (index2 >= len)
            {
                if (arr[index1] < arr[index])
                {
                    //左孩子调整上去
                    temp = arr[index];
                    arr[index] = arr[index1];
                    arr[index1] = temp;
                }
                break;//
            }
            else//左右孩子都有
            {
                if (arr[index1] > arr[index2])//左孩子大于右孩子
                {
                    //放右孩子上去
                    temp = arr[index];
                    arr[index] = arr[index2];
                    arr[index2] = temp;
                    //然后对右边进行调整
                    index = index2;//右孩子作为新的要调整的位置
                }
                else//左孩子小于右孩子
                {
                    temp = arr[index];
                    arr[index] = arr[index1];
                    arr[index1] = temp;
                    index = index1;//左孩子
                }
            }
        }
        return mytemp;
    }

};

int main()
{
    srand((unsigned)time(nullptr));
    Heap myheap;
    for (int i = 0; i < 10; ++i)
    {
        int x=rand() % 100;
        myheap.insert(x);
    }
    for (int i = 0; i < 10; ++i)
    {
        cout << myheap.pop() << '\t';
    }

    cin.get();
    return 0;
}