堆
堆是一种完全二叉树,也是一种优先级队列堆分为大根堆和小根堆,大根堆即对于每一颗树,它的父亲节点的值,一定大于它的孩子节点的值,左右节点的值不用管它的顺序。小根堆同理。
写了一道可以用堆这种数据结构求解的题目,即找数组中第k大的数,要求时间复杂度为O(N)。
解题思路
- 根据堆的定义我们可以知道,这道题用大根堆做是比较合适的。因为堆中它的每一颗子树父节点的是最大的,那么堆顶的元素一定是整个数组里面最大的元素,也就是二叉树的根。那么我们要求出第k个大的元素,就只要先把数组先初始化成一个大根堆,再取出k - 1个堆顶的元素,取出的过程仍然保持成一个大根堆就行了,那么取完之后堆顶的元素就是我们要的结果。
代码实现
void swap(int *a, int i, int j)//交换数组中i和j位置的值
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
void heapinsert(int *a, int index) {//将index下标的数插入到a数组里面并仍然让a数组保持是一个大根堆
while(index >= 0 && a[index] > a[(index - 1) / 2]) {//插入的数比它的父亲节点的值要大,那么它就要交换,因为只有这样才是大根堆
swap(a,index, (index - 1) / 2);//和父亲节点的值做交换
index = (index - 1) / 2;//下标的值变成父亲节点的下标,因为已经交换过了,所以更新下标
}
}
void heapify(int *a, int index, int heapSize)
{
int left = 2 *index + 1;//当前下标的左孩子
while(left < heapSize)//只要还有孩子,就继续堆化,即让数组a保持成一个大根堆。
//如果没有左孩子,那么就肯定没有右孩子,所以不用继续了,也就是没有孩子了
{
int largest = left + 1 < heapSize && a[left + 1] > a[left]? left + 1: left;//指向最大的节点
//如果有右孩子,并且左孩子的值大于右孩子的值,那么左孩子就是两个孩子节点中最大的节点
//如果没有右孩子,那么左孩子就是最大的,因为没有右孩子了
//如果有右孩子,但右孩子的值比左孩子的值大,那么右孩子就是两个孩子节点中最大的节点
largest = a[largest] > a[index]? largest:index;
//如果两个孩子中节点值最大的值大于index这个下标的值,那么最大的节点还是它本身,否则是index
if (largest == index) {//如果最大节点是index,那么代表它已经是一个大根堆了,跳出循环
break;
}
swap(a, largest, index);//和最大的节点交换
index = largest;//index往后面走,继续找,直到index的值比两个孩子节点的值要大。
left = index * 2 + 1;//更新左孩子的下标
}
}
int findKthLargest(int* nums, int numsSize, int k) {
int heapSize = numsSize;
for (int i = 0; i < numsSize; i++) {
heapinsert(nums, i);//把数组初始化成为一个大根堆
}
while(--k){//执行k - 1次把堆顶元素移除
swap(nums, 0, --heapSize);//移除堆顶元素
heapify(nums, 0, heapSize);//让移除之后的数组仍然是一个大根堆
}
return nums[0];//返回堆顶元素,即第k大的数
}
标签:11,总结,index,int,孩子,2023,大根堆,节点,left
From: https://www.cnblogs.com/lwj1239/p/17852650.html