堆，Top-K, 堆排序 ---详解_topk 堆排

堆，Top-K, 堆排序 —详解

堆的概念

注意： 数据结构中的堆跟操作系统对内存划分的堆没有关系，他们是两种学科里面的不同物种。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

• 大堆: 树中一个树及子树中，任何一个父亲都大于等于孩子

• 小堆： 树中一个树及子树中，任何一个父亲都小于等于孩子

建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明。假设采用向下调整法创建堆，且每次都是最坏的情况，即每层的每个节点都要调整到最后一层，那么根节点就要调整（高度）h-1次，第二层的节点就要调整h-2次，第h-1层的节点就要调整1次。

假设采用向上调整法创建堆，且每次都是最坏的情况，即每个新插入堆的节点都要移动到第一层，那么新插入节点就要移动（高度）h-1层，倒数第二层的节点就要移动h-2层，第二层节点就要移动1层，第一层节点就要移动0层。

​

堆的实现

思路：由堆的概念和性质可知，堆的存储结构其实就是一个顺序表，不过逻辑上的结构却不是顺序表，故堆的一些操作也不会跟顺序一样。需要注意的是向上调整算法和向下调整算法，这两个是堆的核心！

堆的初始化和销毁

思路：与顺序表的创建和销毁一模一样。

typedef int Datatype;

typedef struct Headnode
{
	Datatype* arr;
	int size;
	int capacity;
}Hd;

//初始化
void Hdinit(Hd*p)
{
	p->arr = NULL;
	p->size = p->capacity = 0;
}

//销毁
void Hddestory(Hd* p)
{
	assert(p);
	free(p->arr);
	p->capacity = p->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

堆的插入和向上调整算法

思路：堆的插入也要判断堆是否满，与顺序表的插入前的操作一样，不过，堆在尾部插入数据之后，还需用向上调整算法将数据调整一下，使其满足堆的结构。

//插入
void Hdpush(Hd* p,Datatype x)
{
	assert(p);
	if (p->capacity==p->size)
	{
		int newcapacity = p->capacity == 0 ? 4 : sizeof(p->arr) * 2;
		Datatype* tmp = (Datatype*)realloc(p->arr, sizeof(Datatype) * newcapacity);
		assert(tmp);
		p->arr = tmp;
		p->capacity = newcapacity;
	}
    //插入数据到堆的尾部后，size++，使指针指向最后一个元素的后一位
	p->arr[p->size] = x;
	p->size++;
    //调用向上调整算法，使新的数组满足堆结构
	Adjustup(p->arr,p->size-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

向上调整算法

//向上调整
void Adjustup(Datatype* pa, int sz)
{
    //将最后一个元素的下标赋值给child
	int child = sz;
    //通过孩子节点的下标求其父节点的下标
	int parent = (child - 1) / 2;
	while (child)
	{
        //实现的堆是大堆，故父节点必须都大于孩子节点
        //比较父节点和孩子节点，满足条件则交换
        //若实现的是小堆，就要父节点需小于孩子节点，这里就要换成小于号
		if (pa[child]>pa[parent])
		{
			int tmp = pa[child];
			pa[child] = pa[parent];
			pa[parent] = tmp;
		}
		else
		{
			break;
		}
        //将父节点的下标赋值给孩子节点，重新根据孩子节点计算父节点
        //重复上面的步骤，直到满足堆的条件
		child = parent;
		parent = (child - 1) / 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

堆的删除和向下调整算法

思路：堆的删除一般都是删除堆顶的数据，不是删除堆的最后一个数据。删除堆顶不能直接将堆顶删除，这样堆的结构就被改变了，很有可能删除后就不是堆了。故应该先将堆顶的数据与堆尾的数据交换，然后size–，就删除了堆顶，然后再对堆进行向下调整，重新选出堆顶。

//删除---删除堆顶的数据
void Hdpop(Hd* p)
{
	assert(p);
	assert(!Hdempty(p));
	Datatype tmp = p->arr[p->size - 1];
	p->arr[p->size - 1] = p->arr[0];
	p->arr[0] = tmp;
    //删除堆顶
	p->size--;
    //使用向下调整算法调整堆
	Adjustdown(p->arr,p->size-1,0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

向下调整算法

前提：左右子树都是小堆或者大堆

//向下调整
void Adjustdown(Datatype* pa, int sz,int parent)
{
	//左孩子下标为child，那右孩子下标就是child+1
	int child = parent * 2 + 1;
    //循环终止的条件为左孩子或右孩子的下标大于等于堆的长度
	while (child<sz)
	{
		//根据调整的是大堆还是小堆，来选出值大的孩子还是值小的孩子
		//这里是小堆，故选出值小的孩子去与父节点比较
		if (child+1<sz&&pa[child]<pa[child+1])
		{
			child++;
		}
        //根据调整的是大堆还是小堆，来决定是否交换
		//这里是小端，父节点需交换比自己小的孩子节点
		if (pa[parent]>pa[child])
		{
			int tmp = pa[child];
			pa[child] = pa[parent];
			pa[parent] = tmp;
            //交换后将父节点移动到孩子节点的位置，
            //然后再根据父节点的新下标重新计算孩子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

取堆顶元素和堆的元素个数及堆的判空

思路：与顺序表的操作差不太多。

//堆中元素个数
int Hdsize(Hd* p)
{
	assert(p);
	return p->size;
}

//取堆顶的元素
Datatype Hdtop(Hd* p)
{
	assert(p);
	assert(!Hdempty(p));
	return p->arr[0];
}

//判空
bool Hdempty(Hd* p)
{
	assert(p);
	return p->size==0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

ToP-K

问题描述

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能

数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1.用数据集合中前K个元素来建堆

• 前k个最大的元素，则建小堆
• 前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

代码实现

//TOPK问题
//求N个数中最大的前k个数  或 求k个数中最小的前k个数
void TOPK(int* arr, int n, int k)
{
	assert(arr);
	//建立一个长度为k的堆，并初始化，用于保存arr数组中的k个数据
    //并且该堆为小堆
	Hd s;
	Hdinit(&s);
	for (int i = 0; i < k; i++)
	{
		Hdpush(&s, arr[i]);
	}
	//将堆顶的数跟剩下的n-k个数比较，小于就替换
	//然后再采用向下调整，保证堆顶是最小值
	for (int j = k; j < n; j++)
	{
		if (Hdtop(&s)<arr[j])
		{
			s.arr[0] = arr[j];
			Adjustdown(s.arr, k,0);
		}
	}
	//打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", s.arr[i]);
	}
	Hddestory(&s);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

堆排序

注意

升序-----构建大堆

降序-----构建小堆

方法一：

思路：直接用上面写好的堆的数据结构，将数组a的元素全部入到小堆中去，堆顶就是最小的数，然后把堆顶赋值给数组a，再pop掉。（pop函数中包含了向下调整函数）空间复杂度是O(N)

//堆排序问题
void Heapsort(int*a,int sz)
{
	Hd h;
	Hdinit(&h);
	for (int i = 0; i < sz; i++)
	{
		Hdpush(&h, a[i]);
	}
	//堆顶就是最小数，将堆顶赋值给a
	//再pop掉，新的堆顶就是第二小的数
	for (int i = 0; i < sz; i++)
	{
		a[i] = Hdtop(&h);
		Hdpop(&h);
	}
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二：

思路：

void Heapsort(int* a, int n)
{
    //向上调整算法
    //构建小堆
    //第一个数看作堆，后面的数据依次加入堆，然后用向上调整构建堆
    for(int i=1;i<n;i++)
    {	
        //利用插入的思想构建堆
        Adjustup(a,i);
    }
    
    //排升序就要构建大堆，堆顶为最大的数，与堆尾交换后，最大的数被放到了堆尾
    //迭代完成后，最小的数就被放在了最前面
    
    //向下调整算法
    //从最后一个节点的父节点开始倒着调
    //调完后，数组为小堆
	for (int i = (n-1-1)/2; i >=0; i--)
	{
        //利用迭代的思想构建堆
		Adjustdown(a, n, i);
	}
    //堆顶为最小的元素，将堆顶与堆尾交换
    //然后再让堆的长度减一，就把最小的元素拿出来了
    //再对剩下的元素调整，选出新的堆顶，即第二小的元素，再替换掉堆尾
	for (int i = n-1; i >=0; i--)
	{
		int tem = a[0];
		a[0] = a[i];
		a[i] = tem;
        //向下调整
		Adjustdown(a, i, 0);
	}
    //打印
	for (int i = 0; i <n; i++)
	{
		printf("%d ", a[i]);
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

总结

这章的干货还是挺多的，堆的数据结构本身并不算很难把握，本章的重点难点就是向下调整算法和向上调整算法，还有一些堆的性质，例如堆是完全二叉树，最后一层的节点必须是连续的，且堆只有两种结构，即大堆和小堆等性质，还有孩子节点的下标和父节点的下标的关系式。