堆

概念

最大堆:最上面的结点数值最大

特点:
1.每个结点最多可以有两个结点

2.根结点的键值是所有结点中最大的，每个结点的值都比孩子的值大。

3.除了根节点没有兄弟结点，最后一个左子结点可以没有兄弟结点，其他结点必须有兄弟结点。(有这个限制，下面的求子结点和父结点的公式才能成立。)

最小堆:最上面的结点数值最小....其他同最大堆

堆是最有个性的树，用数组表示的树。

在数组中快速创建堆

左图——》右图

1.找到最后一个结点的父结点，(该父结点)与其子结点进行比较大小，若某个子结点大于父结点，则与该父结点交换位置。(就是从最后一个非叶子结点开始进行调整，(向下调整就是找到该父结结点的子结点，进行调整。))

2.再移动到前一个父结点，进行上述操作。

3......

补充:static修饰的全局函数

一个普通的全局的静态函数。. 这样的static函数与普通函数的区别是：用static修饰的函数，限定在本源码文件中，不能被本源码文件以外的代码文件调用。

链接——链接

相关接口实现

//堆的结构
typedef struct _Heap
{
    int* arr;
    int size;
    int capacity;
}Heap;


void buildHeap(Heap& hp);
void adjustDown(Heap& hp, int index);
bool insertHeap(Heap& hp, int val);

//堆的初始化
bool initHeap(Heap& hp, int* orginal, int size)
{
    int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;
    hp.arr = new int[capacity];
    if (!hp.arr)
    {
        return false;
    }
    hp.capacity = capacity;
    hp.size = 0;

    //如果存在原始数据则构建堆
    if (size > 0)
    {
        //方式1：直接全部拿过来
        /*_memccpy(hp.arr, orginal, size, size * sizeof(int));
        hp.size = size;
        buildHeap(hp);*/

        //方式2：一个一个插入 ，插一次排一次
        for (int i = 0; i < size; i++)
        {
            insertHeap(hp, orginal[i]);
        }
    }
    return true;
}

//构建堆
void buildHeap(Heap& hp)
{
    for (int i = ((hp.size - 1)-1) / 2; i >= 0; i--)
    {
        adjustDown(hp, i);
    }
}

//向下调整——根据已经有的数据内容进行调整
void adjustDown(Heap& hp,int index)
{
    int cur = hp.arr[index];//当前父节点的值
    int parent = 0;//索引
    int child = 0;
    //调整是一个循环的过程，整个向下
    //能够进入循环的条件，它得有左子结点。
    for (parent = index; (parent * 2 + 1) < hp.size; parent = child)//for循环的最后一个参数，定位新的父结点索引
    {
        //从最后一个父结点开始，父结点肯定有左孩子
        child = parent * 2 + 1;
         
        //取两个子结点中较大的一个
        if (((child + 1) < hp.size) && hp.arr[child] < hp.arr[child + 1])
        {
            child++;//如果右边的孩子大，那就拿到右边孩子的下标
        }
    
        //将子结点与父结点进行对比
        if (cur >= hp.arr[child])
        {
            break;//如果在高层，此时父结点大于子结点就break,因为是从底层上来的，比父结点都大
        }
        else
        {
            hp.arr[parent] = hp.arr[child];
            hp.arr[child] = cur;
        }
    }
}

//向上调整——对新插入的元素进行调整
void adjustUp(Heap& hp, int index)
{
    while (index > 0)
    {
        int temp = hp.arr[index];//要插入的结点
        int parent = (index - 1) / 2;
        if (temp > hp.arr[parent])
        {
            hp.arr[index] = hp.arr[parent];
            hp.arr[parent] = temp;
            index = parent;
        }
        else
        {
            //如果已经小于等于父亲的值了
            break; 
        }
    }
}

//加入新的元素
bool insertHeap(Heap& hp, int val)
{
    if (hp.size == hp.capacity)
    {
        return false;
    }
    int index = hp.size;//保存新加入元素的位置，因为size要++
    hp.arr[hp.size++] = val;
    adjustUp(hp,index);
    return true;
}

//打印输出堆中元素
void printHeap(Heap& hp)
{
    int num = hp.size;
    int front = 0;
    int back = 1;
    int row = 1;
    while (num)
    {
        for (int j = front; j < back; j++)
        {
            cout << hp.arr[j] << " ";
        }
        cout << endl;
        num -= row;//输出完本行还剩的元素个数
        //如果减去本行输出的个数小于0
        if (num <= 0)
        {
            break;
        }
        row *= 2;//下一行要输出的元素个数

        front = back;//定位下一行的起点

        if (num - row <= 0)//如果当前的元素个数不够输出下一行的，直接定位下一行的back位置
        {
            back = hp.size;
        }
        else// 够则——手动定位结尾位置
        {
            back += row;
        }
    }

}

//弹出堆顶元素
void popTop(Heap& hp)
{
    hp.arr[0] = hp.arr[hp.size - 1];
    hp.size--;
    buildHeap(hp);

}

构建堆 and 向下调整的图解

补充——打印输出

堆插入元素按升序(降序)排序的效率时很高的，因为只需要和父亲比较。父亲的父亲......

应用

构建优先队列

操作系统内核作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

如果最小键值元素拥有最高的优先级，那么这种优先队列叫作 升序优先队列（即总是先删除最小 的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作 降序优先队列 （即总是先删除最大的元素）；由于这两种类型是完全对称的，所以只需要关注其中一种。

核心实现同上建最大堆，就是把其中的数据换成了Task(任务，里面包括优先级，等其他属性)，根据优先级的大小，来创建堆。

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特 点快速定位指定索引的元素。

选择排序工作原理:第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置， 然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

类似于上面构建最大堆时的弹出堆顶元素。只是不将最后一个元素删除(不size--)，而是不断的将建好的大堆堆顶元素放到最后。

#include<iostream>
using namespace std;

void adjustDown(int* ary, int index, int tatal)
{
    int cur = ary[index];
    int parent = 0;
    int child = 0;

    for (parent = index; (parent * 2 + 1) < tatal; parent = child)
    {
        child = parent * 2 + 1;
        if (((child + 1) < tatal) && (ary[child] < ary[child + 1]))
        {
            child++;
        }
        
        if (cur >= ary[child])
        {
            break;
        }
        else
        {
            ary[parent] = ary[child];
            ary[child] = cur;
        }
    }
}


void HeapSort(int* ary,int size)
{
    int tempS = size;
    //先用这个数组键一个堆
    for (int i = (size - 1 - 1) / 2; i >= 0; i--)
    {
        adjustDown(ary, i, tempS);
    }
    //必须要先建好一个堆
    //因为这样将堆顶元素和堆尾元素交换之后，除了堆顶新换过来了元素，“仍”是一个最大(小)堆，因为比较就要和父节点比。
    
    int front = 0;
    int back = tempS - 1;
    for (;back > 0; back--)
    { 
        int tempChange = ary[front];
        ary[front] = ary[back];
        ary[back] = tempChange;
        adjustDown(ary, front, --tempS);
    }    
}

int main(void)
{
    int arraY[] = {3,1,2,4,56,7,89,99};
    int size = sizeof(arraY) / sizeof(arraY[0]);

    HeapSort(arraY, size);

    for (int i = 0; i < size; i++)
    {
        cout << arraY[i] << " ";
    }
    return 0;
}