在开始这一节的内容之前,我们先来回顾一下与堆相关的重点:
1、堆是二叉树顺序存储结构的一个具体体现,堆中每个节点的值总是不大于或不小于其父节点的值 (大堆/小堆),堆总是一棵完全二叉树,堆使用顺序表存储元素; 2、堆中父节点下标的计算公式:(n-1)/2,左孩子下标:n*2+1,右孩子下标:n*2+2; 3、堆只能在尾部插入数据,且插入数据后需要保证堆的结构,所以在插入数据之后我们要进行向上调整,向上调整的时间复杂度为O(log N) (log 以2为底) ; 4、堆只能在头部删除数据,且删除数据后需要保证堆的结构,又因为顺序表头删需要挪动数据,效率很低,所以在堆删除数据会先将堆顶和堆尾的数据进行交换,然后让 size–,再进行向下调整,向下调整的时间复杂度为O(log N) (log 以2为底) 。
堆排序是选择排序的一种,它的时间复杂度为 O(N*logN),空间复杂度为 O(1)。
堆排序的第一步就是建堆,建堆有两种方法:向上调整建堆和向下调整建堆。
向上调整建堆: 把数组的第一个元素作为堆的根节点,然后在堆尾依次插入其余元素,每插入一个元素就向上调整一次,从而保证堆的结构;
向上调整建堆的时间复杂度: 由于堆是完全二叉树,而满二叉树是完全二叉树的一种,所以此处为了简化计算,使用满二叉树来得出时间复杂度 (时间复杂度本身看的就是近似值,多几个节点不影响最终结果):
如上图,我们把每一次的节点个数除以每一个节点需要调整的次数,最后再求和,就可以得到一共需要调整的次数;然后再根据满二叉树节点总数与树的高度的关系将表达式中的h替换掉,最终可以得到向上调整建堆的时间复杂度为:O(N*logN);
向下调整建堆: 从倒数第一个非叶子节点 (即最后一个叶节点的父节点) 开始向下调整,直到调整到根。
向下调整建堆的时间复杂度:
如上图,向下调整建堆的时间复杂度为:O(N);
综合上面两种建堆方法,建堆的时间复杂度为:O(N);
现在我们建堆工作已经完成了,接下来就是选数,假设现在我们要排升序,那么方法一共有三种:
1、建小堆,开辟一个和原数组同等大小的新数组,每次取出堆顶的元素 (最小的元素) 放在新数组中,然后挪动数组中的数据,最后排好序以后再将新数组中的数据覆盖至原数组;
缺点:每次挪动数据的效率很低,且挪动数据会造成堆中其余元素父子关系混乱,需要重新建堆,而建堆的时间复杂度也是O(N),所以二者嵌套后时间复杂度:O(N^2),空间复杂度:O(N);
2、也是建小堆,不过这次我们借鉴堆 pop 数据的方法,先将堆顶的元素放入新数组中,然后交换堆顶和堆尾的元素,之后再向下调整数组中前 n-1 个数据,直到排好序,最后将排好序以后再将新数组中的数据覆盖至原数组;
缺点:虽然此方法可以让我们每次都拿到数组中最小的元素,但是需要开辟额外的空间,时间复杂度:O(N*logN),空间复杂度:O(N);
3、建大堆,先将堆顶和堆尾的数据进行交换,使得数组中最大的元素处于数组末尾,然后向下调整前 n-1 个元素,使得次大的数据位于堆顶,最后重复前面的步骤,把次大的数据存放到最大的数据之前,直到数组有序;
优点:没有额外的空间消耗,且效率达到了 O(N*logN);
综合上面三种选数的方法,选数的时间复杂度为:O(N*logN),空间复杂度为:O(1);
//交换两个节点
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上调整 -- 大堆
void AdjustUp(int a[], int child)
{
int parent = (child - 1) / 2; //找出父节点
while (child > 0) //当调整到根节点时不再调整
{
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
}
else
{
break;
}
//迭代
child = parent;
parent = (child - 1) / 2;
}
}
//向下调整 -- 大堆
void AdjustDown(int a[], int n, int parent)
{
int maxchild = parent * 2 + 1; //找到左孩子(左孩子+1得到右孩子)
while (maxchild < n) //调整到数组尾时不再调整
{
if (maxchild + 1 < n && a[maxchild + 1] > a[maxchild])
{
maxchild += 1;
}
if (a[parent] < a[maxchild])
{
Swap(&a[parent], &a[maxchild]);
}
else
{
break;
}
//迭代
parent = maxchild;
maxchild = parent * 2 + 1;
}
}
void HeapSort(int a[], int n)
{
//建堆 -- 向上调整建堆:O(N*logN)
//int i = 1;
//for (i = 1; i < n; i++)
//{
// AdjustUp(a, i);
//}
//建堆 -- 向下调整建堆:O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--) //n-1找到最后一个叶节点,该节点-1/2找到倒数第一个父节点
{
AdjustDown(a, n, i);
}
//排序 -- 升序(建大堆,向下调整):O(N*logN)
for (int i = n - 1; i > 0; i--)
{
Swap(&a[i], &a[0]); //交换堆尾和堆顶的元素
AdjustDown(a, i, 0); //向下调整
}
}
int main()
{
int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };
int n = sizeof(a) / sizeof(a[0]);
//堆排序
HeapSort(a, n);
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大;比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是,如果数据量非常大,排序就不太可取了 (数据都不能一下子全部加载到内存中),最佳的方式就是用堆来解决,基本思路如下:
第一步:用数据集合中前K个元素来建堆 – 前k个最大的元素,则建小堆;前k个最小的元素,则建大堆;
第二步:用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素;
//交换两个节点
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整 -- 小堆
void AdjustDown(int a[], int n, int parent)
{
int minchild = parent * 2 + 1; //找到左孩子(左孩子+1得到右孩子)
while (minchild < n) //调整到数组尾时不再调整
{
if (minchild + 1 < n && a[minchild + 1] < a[minchild])
{
minchild += 1;
}
if (a[parent] > a[minchild])
{
Swap(&a[parent], &a[minchild]);
}
else
{
break;
}
//迭代
parent = minchild;
minchild = parent * 2 + 1;
}
}
int* TopK(int a[], int n, int k)
{
//开辟K个元素的空间
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
return NULL;
}
//将数组前K个元素拷贝到新空间
for (int i = 0; i < k; i++)
{
minHeap[i] = a[i];
}
//建小堆 -- 向下调整建堆:O(N)
for (int i = (k - 1 - 1) / 2; i >= 0; i--) //n-1找到最后一个叶节点,该节点-1/2找到倒数第一个父节点
{
AdjustDown(minHeap, k, i);
}
//取后N-k个元素与堆顶元素比较,如果大于堆顶元素,就入堆
for (int i = k; i < n; i++)
{
if (minHeap[0] < a[i])
{
minHeap[0] = a[i];
AdjustDown(minHeap, k, 0);
}
}
return minHeap;
}
int main()
{
int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };
int n = sizeof(a) / sizeof(a[0]);
//TopK问题 -- 前K个最大的元素
int k = 3;
int* ret = TopK(a, n, k);
for (int i = 0; i < k; i++)
{
printf("%d ", ret[i]);
}
free(ret);
ret = NULL;
return 0;
}