@[TOC]
前言:
- 博主收集的资料,连载中。
- 转载请标明出处:New Young
- 本文介绍 ==堆==—-一种特殊的==完全二叉树==.
堆
堆的概念
如果完全二叉树中,==所有的==
父亲结点
的值都比其左右孩子结点
的值大或者小,这种完全二叉树称为堆
,
- 其中将父亲结点大于孩子结点的称为==大堆==.
- 父亲结点小于孩子结点的称为==小堆==.
堆的特点
- 堆是一种
特殊的
完全二叉树- 根结点的值是==最值.==
- 堆中某个节点的值总是不大于或不小于其父节点的值 ,即大的值或者小的值总是沉到更下层.
堆的存储
堆是一种
完全二叉树
,为了避免不必要的空间浪费,一般用==顺序存储(数组)==的形式来存储数据.typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap;
堆的功能实现
- 堆的很多功能(堆的创建,堆排序,TopK问题等)都需要向==上或者向下调整算法==,因此先介绍这2个,再介绍其它功能。
向上调整算法
//向上调整。 void Adjustup(HPDataType* a, int child) { assert(a); int parent = (child - 1) / 2;//无论左右孩子,都可以. while (child>0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
向下调整算法
- 从根结点向下调整前,
左右子树
必须满足堆要求—-==堆中某个节点的值总是不大于或不小于其父节点的值。==
//向下调整 void Adjustdown(HPDataType* a, int n, int parent) { assert(a); int child = 2 * parent + 1; while (child < n)//完全二叉树的特点,当无左子树时,代表达到领界或者越界。 { if ( child+1<n && (a[child+1] < a[child])) { child ++; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }
向上与向下调整的比较
算法 | 特点 | 使用的范围 | 联系 |
---|---|---|---|
向上调整 | 从堆的尾开始的调整,结点总是在从根结点到该结点的路径上移动 | 堆的插入(Push),堆的创建(Create), | 二者没然的联系,主要看我们的使用角度 |
向下调整 | 从堆的头开始的调整,调整前,根结点的左右子树必须满足堆的要求。 | 堆的删除(Pop),堆的创建(Create),TopK问题,堆排序 | |
堆的插入
堆的插入从
尾部
进行插入。// 堆的插入 void HeapPush(Heap* hp, HPDataType x) { assert(hp); HeapIsExpandCapacity(hp); hp->_a[hp->_size++] = x; //因为插入元素前,仍是一个堆,只需要要向上调整,就可以让插入的元素走到正确的位置 Adjustup(hp->_a,hp->_size-1); }
堆的删除
堆的删除方式很特殊:
先将根结点与尾结点进行交换,之后从根结点进行向下调整,直到尾结点前
/ 堆的删除,堆的删除删的是跟结点 void HeapPop(Heap* hp) { assert(hp); Swap(&hp->_a[0], &hp->_a[hp->_size - 1]); --hp->_size; Adjustdown(hp->_a, hp->_size, 0); }
堆的扩容
//是否扩容 void HeapIsExpandCapacity(Heap* hp) { if (hp->_size == hp->_capacity) { hp->_capacity = hp->_capacity == 0 ? 4 : 2 * (hp->_capacity); HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)*hp->_capacity); if (tmp == NULL) { printf("Expand Is Failure\n"); exit(-1); } hp->_a = tmp; } }
堆的创建
堆的创建有2种主要形式:
- 通过==向上调整==的算法,–直接在给定数组上进行建队,
- 通过==向下调整==的算法,通过给定数组的数据,动态规划,重新建立堆。
非原数组,动态建立
效果图
代码
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
//方式一:不直接在数组上操作,重新构建一个堆
for (int i = 0; i < n; ++i)
{
HeapPush(hp, a[i]);
}
printf("向上调整结果\n");
HeapPrint(hp->_a, hp->_size);
}
原数组
向上调整法:
- 只有一个结点的堆也堆,因此我们从下标1开始插入堆,然后向上调整,重复这个过程直到建堆完成。
代码
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
////思路:只有一个结点也是堆,通过插入,向上调整,建堆。
for (int i = 1; i < n; ++i)
{
Adjustup(a, i);
}
HeapPrint(a, n);
}向下调整法
向下循环法
因为堆是一种递归结构,这表明如果我们再向下调整整个堆前,可以先调整它的左右子树,通过这种递归,最终我们需要从非叶结点的父亲结点回推
效果展示
代码
//思路:只有一个结点也是堆,通过插入,向下调整,建堆。
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
for (int parent = (n - 1 - 1) / 2; parent >= 0; --parent)
{
Adjustdown(a, n, parent);
}
}
递归法
代码
void RecDown(HPDataType* a, int n, int parent)
{
assert(a);
int child = 2 * parent + 1;
if (child >= n )
{
Adjustdown(a, n, parent-1);
return;
}
else
{
RecDown(a, n, parent + 1);
Adjustdown(a, n, parent);
}
}
建堆的创建时间复杂度证明
堆排序
思路
我们再删除堆操作中,先将头尾交换,之后对头==向下调整==。再结合堆的==根结点==是最值
.如果我们每次都将堆的根结点与尾交换,然后将尾前面就行==向下调整==,这样就可以完成排序。如果想
降序
,因为最大值
在最后,所以要求第一个根结点
是==最大值==,这就要求我们建==大堆==,让根结点
成为==最大值==。反之,==升序==,建小堆
。
效果
代码
// 降序,建小堆,跟结点必然是最小结点,
//所以首尾交换后,跟的左右子树仍是关系未破坏的堆,
//所以可以通过向下调整的方式,再次选出最小的结点,
//重复改过程。
void HeapSort(HPDataType* a, int n)
{
assert(a);
//建堆
//
//
//
//方式一:向上调整算法
//for (int i = 1; i < n; ++i)
//{
// Adjustup(a, i);
//}
//HeapPrint(a, n);
//方式二,非递归向下调整算法。
//方式二:在数组上操作
//思路:只有一个结点也是堆,通过插入,向下调整,建堆。
//for (int parent = (n - 1 - 1) / 2; parent >= 0; --parent)
//{
// Adjustdown(a, n, parent);
//}
//printf("向下调整结果\n");
//HeapPrint(a, n);
////方式三,递归向下调整算法建堆
//
//递归法建堆
printf("递归向下调整结果\n");
RecDown(a, n, 0);
for (int i = 0; i < n-1; ++i)
{
Swap(&a[0], &a[n -1- i ]);
Adjustdown(a, n-1-i, 0);
}
}
TopK问题
思路:
问题:如果有10亿个数,找出其中最大的前10。首先10亿个数,只能将他们先存到文件中,之后取和适数量放到内存中。
这里为了方便,假设文件存放了N(我实际假设环境是100个数)个数,一次取t个数存入内存,需要K次。
如果我们用排序的思想—-这里用选择法,时间复杂度为:0(K*N^2)
发现很大,效率不高。
我们观察
堆
,发现,堆的根结点是最值
,根以下的结`点`都大于或者小于根结点,如果我们将除了==建堆以外==的数据与==根结点==比较,如果
大于
根结点,就替换
根结点,同时进行==向下调整==,这样的话大数
就==沉到==下面了,而==最小的,次小等等==都会因为根结点而被==替换==调。如果要找最大的前K个,那么必须建小堆,如果建大堆,如果根结点恰好是最大的一个,这就会Creash。但是建小堆就不用担心,根结点是最小的,不会Creash。
文件存储数据代码
效果
int main ()
{
srand(time(NULL));
FILE* pf = fopen("C:\\Users\\Administrator\\Desktop\\test.txt","w");
assert(pf);
for (int i = 0; i < 100; ++i)
{
fprintf(pf, "%d ", rand()%100);
}
return 0;
}
TopK代码
效果
代码
//找最大的 k个,则建立小堆,因为大堆可能会导致最大的丢失。
//先去文件中的前N个放到数组中,建成小堆,之后继续将数据重新放到数组中,然后依次比较堆根结点。直到EOF。
void TopK( int n, int k)
{
FILE* pf = fopen("C:\\Users\\Administrator\\Desktop\\test.txt", "r");
assert(pf);
Heap hp;
HeapInit(&hp);
int* a = (int*)calloc(k ,sizeof(int));
assert(a);
//建小堆
for (int i = 0; i < k; ++i)
{
if (feof(pf))
{
break;
}
else
{
fscanf(pf, "%d ", &a[i]);
}
}
HeapPrint(a, k);
//这里不能在原数组上建堆。动态建堆
HeapCreate(&hp, a, k);
printf("建的小堆:");
HeapPrint(hp._a, hp._size);
while (!feof(pf))
{
int i = 0;
for ( i = 0; i < k; ++i)
{
if (feof(pf))
{
break;
}
else
{
fscanf(pf, "%d ", &a[i]);
}
}
for (int j = 0; j < i; ++j)
{
if (a[j] > HeapTop(&hp))
{
hp._a[0] = a[j];
Adjustdown(hp._a, k, 0);
}
}
}
HeapPrint(hp._a, hp._size);
HeapDestory(&hp);
free(a);
a = NULL;
}