堆的创建及应用-详细解释

2024年4月22日 互联网

堆（英语：heap)通常是一个可以被看做一棵树的数组对象。
堆总是满足下列性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）
如下图示：
这里写图片描述
小堆(大堆)中：任一结点的关键码均小于(大于)等于它的左右孩子的关键
码，位于堆顶结点的关键码最小(最大)，从根节点到每个结点的路径上数
组元素组成的序列都是递增(递减)的

  1. 创建堆
void AdjustDownBig(DataType* a, size_t n, int root)//向下调整
{size_t parent = root;size_t child = 2 * parent + 1;//孩子节点while (child < n){if (a[child] < a[child + 1] && child + 1 < n)//取孩子节点最较大值{child++;}if (a[child] > a[parent])//孩子大于父亲，交换值{DataType tmp = a[child];a[child] = a[parent];a[parent] = tmp;parent = child;//继续向下调整child = 2 * parent + 1;}else{break;}}}
void MakeHeap(DataType* a, size_t n)//创建大堆
{int i = (n - 2) >> 1;//从最后一个叶子节点的父亲节点开始调整for (; i >= 0; i--){AdjustDownBig(a, n, i);//i代表父亲节点，n代表调整节点的个数}
}

2.100亿个数中找出最大的前K个数（海量数据top K问题）

void AdjustDownSmall(DataType* a, size_t n, int root)//向下调整小堆的创建
{size_t parent = root;size_t child = 2 * parent + 1;while (child < n){if (a[child] > a[child + 1] && child + 1 < n){child++;}if (a[child] < a[parent]){DataType tmp = a[child];a[child] = a[parent];a[parent] = tmp;parent = child;child = 2 * parent + 1;}else{break;}}}
void TopK(DataType *a, size_t n, size_t k)//简意：取n中最大的前k个
{int i = (k - 2) >> 1;size_t _k = k;for (; i >= 0; i--)//先创建前k个大小的小堆{AdjustDownSmall(a, k, i);}for (i = k; i < n; i++)//从第k+1个就是下标为k的数开始与小堆中根比较{if (a[i] > a[0])//大于根，替换它，并且向下调整，循环往复堆中就是n个数中最大的前k个{a[0] = a[i];AdjustDownSmall(a, k, 0);}}for (i = 0; i < k; i++){printf("%d ", a[i]);}printf("\n");
}
  1. 堆排序
    定义：利用堆进行对一组无序数进行排序
    时间复杂度O(n*logn)
void HeapSort(DataType* a, size_t n)//堆排序
{MakeHeap(a, n);//建大堆for (int i = n ; i > 0; i--){int tmp = a[i - 1];a[i - 1] = a[0];a[0] = tmp;AdjustDownBig(a, i - 1, 0);}for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
  1. 优先级队列
void PriorityQueueInit(PryQueue* q)//初始化
{assert(q);q->_size = 0;for (int i = 0; i<1000; i++){q->_a[i] = 0;}
}
void AdjustUp(DataType* a, size_t n, int child)//向上调整
{size_t parent = (child - 1) >> 1;while (child > 0){if (a[child] < a[parent]){DataType tmp = a[child];a[child] = a[parent];a[parent] = tmp;child = parent;parent = (child - 1) >> 1;}else{break;}}
}
void PriorityQueuePush(PryQueue* q, DataType x)//插入
{if (q->_size == 0){q->_a[q->_size] = x;q->_size++;}else{q->_a[q->_size] = x;q->_size++;AdjustUp(q->_a, q->_size, q->_size - 1);//向上调整，从叶子节点开始，保持大堆}
}
void PriorityQueuePop(PryQueue* q)//删除
{assert(q);q->_a[0] = q->_a[q->_size - 1];//最后一个节点替换根节点，并且节点个数减1，再向下调整q->_size--;AdjustDownSmall(q->_a,q->_size,0);}
DataType PriorityQueueTop(PryQueue* q)//取最大的
{assert(q);return q->_a[0];//返回根节点
}
size_t PriorityQueueSize(PryQueue* q)//返回个数
{assert(q);return q->_size;}
size_t PriorityQueueEmpty(PryQueue* q)//对列是否为空
{assert(q);return q->_size == 0 ? 0 : q->_size;
}

测试优先级队列：

void TestPriorityQueue()
{PryQueue q;PriorityQueueInit(&q);PriorityQueuePush(&q, 5);PriorityQueuePush(&q, 2);PriorityQueuePush(&q, 3);PriorityQueuePush(&q, 7);PriorityQueuePush(&q, 6);PriorityQueuePush(&q, 1);PriorityQueuePush(&q, 4);size_t size = PriorityQueueSize(&q);while (PriorityQueueEmpty(&q) != 0){printf("%d ", PriorityQueueTop(&q));//打印堆的根后，再删堆的根。PriorityQueuePop(&q);}printf("\n");
}

测试结果：
这里写图片描述
需要源代码请戳这里GitHub

最新文章