侧边栏壁纸
  • 累计撰写 278 篇文章
  • 累计创建 3 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

【数据结构】堆(C++)

xuanxuan
2021-10-13 / 0 评论 / 0 点赞 / 5 阅读 / 10469 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2024-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

概念

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vp6Q9cdD-1634094950587)(堆.assets/image-20211012141012636.png)\]

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

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

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

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

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


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


\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UOb5I6sH-1634094950589)(堆.assets/image-20211012142229662.png)\]


在数组中快速创建堆

左图——》右图

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FmF8hPyY-1634094950590)(堆.assets/image-20211012143038239.png)\]

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 向下调整的图解

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TFWFaxvy-1634094950592)(堆.assets/image-20211012163121314.png)\]


补充——打印输出


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

应用

构建优先队列

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

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9pnMKxw5-1634094950594)(堆.assets/image-20211013092337526.png)\]

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


核心实现同上建最大堆,就是把其中的数据换成了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;
}
0

评论区