@[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;
}
