数据结构:堆
文章目录
- 一.堆的概念和性质
- 二.堆的结构
- 三.堆的实现
- 3.1结构体声明
- 3.2堆初始化
- 3.3释放堆
- 3.4打印堆
- 3.5插入
- 3.6删除
- 3.7取堆顶元素
- 3.8堆的元素个数
- 3.9判空
- 3.10补充
- 四.建堆
- 4.1向上调整建堆
- 4.2向下调整建堆
- 五.排序
- 5.1升序
- 5.2降序
- 六.TOP-K问题
一.堆的概念和性质
堆的概念：
堆其实是一种完全二叉树
像这种二叉树，**如果每个父节点都比它的子节点要大，我们把这个二叉树称为最大堆/大根堆，相反，如果每个父节点都比它的子节点要小就是最小堆/小根堆。**上面这张图就是一个小根堆。
堆的性质：
- 堆的某个节点总是不大于或不小于其父节点的值，也就是说这个堆要么是最大堆要么是最小堆。
- 堆总是一个完全二叉树。
二.堆的结构
堆是一种数据结构，但是它是如何存储数据的呢？真的像这样存储的吗？
其实不是的，这只是一种逻辑结构，这是我们想象出来的一种结构，但实际存在内存当中的样子是这样的：
没看错，堆在内存当中其实就是以数组的形式存储的。仔细对比两张图可以发现，数组存储逻辑结构当中的数据是从头节点开始自上而下，自左而右一次存储的：
既然这两种结构是一样的，能不能找一找它们之间的关系呢？
如果0这个下标是父节点的话它的子节点应该就是他后面两个下标为1，2的值，如果父节点为2的话，它的子节点应该是5.
这就可以推断：
左孩子节点 = 父节点 * 2 + 1
右孩子节点 = 父节点 * 2 + 2
我们能通过父节点找到子节点，但我们怎么通过子节点来找到父节点呢？其实很简单：
父节点 = ( 子节点(左/右孩子节点) - 1 ) / 2
虽然通过右孩子来找父节点可以-2在/2，但是可以发现-1也同样可以。
三.堆的实现
3.1结构体声明
typedef int HPDataType;//声明堆的结构体
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
既然已经说过了堆是用数组来实现的，所以我们可以用动态内存开辟来给堆开辟一块空间，指针a就是为了接收这块空间的起始地址。为了方便以后能扩容就在定义两个变量，size:此时数组内的元素个数，capacity:这个数组的最大容量。
3.2堆初始化
//初始化堆
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}
我们一开始先不给这个数组开辟空间，等到后面给堆添加函数的时候在开辟。
3.3释放堆
//释放堆
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}
在整个结构体里只有a指向的空间是动态开辟出来的，所以在程序结束之前要将这块空间释放掉。
3.4打印堆
//打印堆
void HeapPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}
和打印普通数组一样的做法。
3.5插入
//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//向上调整
static void AdjustUp(HPDataType* a, int children)
//从children对应的节点一直到最上面这一块进行调整
{assert(a);int parent = (children - 1) / 2;while (children > 0){if (a[children] > a[parent]){Swap(&a[children], &a[parent]);children = parent;parent = (children - 1) / 2;}else{break;}}
}
//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//插入前先判断是否需要扩容if (php->capacity == php->size){//需要开辟的空间大小HPDataType newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;//开辟了newcapacity个整型的空间HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("HeadPush");exit(-1);}//将刚开辟好的空间的地址传给结构体里的指针变量aphp->a = tmp;php->capacity = newcapacity;}//添加x这个元素到数组末尾php->a[php->size] = x;php->size++;//向上调整成堆//a是需要调整堆这个数组的地址//php->size - 1是说明要从哪个位置开始调整//size-1就说明从堆末尾开始向上调整AdjustUp(php->a, php->size - 1);
}
堆的插入，删除都比较麻烦，因为我们要保证插入/删除之后，这个堆仍然是一个堆，所以在插入之后做相应调整。
插入这一块函数就不多说了，就是普通的数组尾插。这里主要说明向上调整。
此时这里有一个大堆：
我们在末尾插入了一个100：
但是发现插入后这个二叉树已经不是堆了其它节点的关系是父节点>子节点，而100当子节点的时候反而>它的父节点，所以此时我们将他适当调整，用到的方法就是向上调整
调整的方法是先比较此时先插入的节点与它的父节点比较(可以把画圈的那一部分当成需要调整的树)，我们之前的是大堆，所以这里子节点>父节点就交换，反之就说明不用交换直接退出：
但是发现此时的100还要比它的父节点大，所以还要移动，更新parent,children两个变量的值，并且重新做一遍刚才的内容。
这就是向上调整的整个过程：
//向上调整
static void AdjustUp(HPDataType* a, int children)
//从children对应的节点一直到最上面这一块进行调整
{assert(a);//先找到父节点和子节点的位置int parent = (children - 1) / 2;while (children > 0){//比较if (a[children] > a[parent]){Swap(&a[children], &a[parent]);//更新两个变量的值，让他们指向更新后的父节点，子节点children = parent;parent = (children - 1) / 2;}//如果发现比较结果不一样说明此时已经完成调整直接返回else{break;}}
}
我们将循环条件设置为children > 0，因为children这个变量=0的时候说明它在堆顶位置，不可能有父节点所以在此之前结束就行。
这里还用到Swap函数，很简单，单纯的是为了改变两个元素
//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
3.6删除
//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整
static void AdjustDown(HPDataType* a, int n, int parent)
//从此时父节点一直到末尾这一块结束
{assert(a);//假设左孩子最大int child = parent * 2 + 1;while(child < n){//如果刚才假设错了，child指向的就是左孩子右边的右孩子if (child + 1 < n && a[child] > a[child + 1]){child++;}//到了这里child永远指向的是两个孩子最大的那一个if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}//删除
void HeapPop(HP* php)
{assert(php);assert(php->size);//交换头和尾Swap(&php->a[0], &php->a[php->size - 1]);//交换完之后把最后一个元素删掉，也就是后来的向下调整不考虑它php->size--;//向下调整//a代表需要调成的堆的位置//php->size是需要调整的堆的元素个数//从哪里开始调整，这里传0是说明从堆顶开始AdjustDown(php->a, php->size, 0);
}
这里删除的是堆顶元素，如果删除最后的那个元素，就太简单了 没啥意义了。
但是直接删除堆顶元素的话，剩下的可能在删除后就构建不成一个堆了，所以在这里在用一个向下调整的方法。
在进行调整之前将堆顶的元素与最后的元素互换，换完之后我们将除了最后一个元素的元素看成一个堆：
交换完之后就可以进入到调整部分了，先找到此时堆顶节点和它两个孩子中最大的那个节点
但是为什么找到的是最大的那个孩子呢？因为我们这里的主要目的是构成一个堆，如果我们希望构成一个大堆，如果父节点小于子节点就互换，但是我们换的是子节点里小的那个节点，就会造成原来大的子节点变成小的子节点的儿子，这显然不符合大堆。所以将父节点与最大的节点比较：
如果父节点小就互换：
换完之后如果没有结束就更新child,parent的位置，然后重新走一遍刚才的步骤：
这样不断循环一直向下调整就把堆给调整好了。
这里循环的终止条件是child < n。n是这个数组元素的大小如果child>=n就说明数组越界了，这显然不合理。
还有要注意的一点是：
if (child + 1 < n && a[child] < a[child + 1])
{child++;
}
判断大孩子节点的这一块，里面条件要加上child + 1 < n
加入此时父节点是25，但是它只有一个左孩子节点
如果强行让这个左孩子与右孩子相比较，右孩子就会造成数组越界。所以在这里要多加一个限制条件。
3.7取堆顶元素
//取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size);return php->a[0];
}
3.8堆的元素个数
//堆的元素个数
size_t HeapSize(HP* php)
{assert(php);return php->size;
}
3.9判空
//判空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}
3.10补充
刚才讲的主要是大堆，如果希望是一个小堆把上面代码中child和parent比较的条件改一下就行。
//建大堆
if (a[children] > a[parent])if (child + 1 < n && a[child] > a[child + 1])
{child++;
}
if (a[parent] > a[child])
{Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;
}
//建小堆
if (a[children] < a[parent])if (child + 1 < n && a[child] < a[child + 1])
{child++;
}
if (a[parent] < a[child])
{Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;
}
四.建堆
我们刚才讲的是插入/删除一个元素并且保证结果仍然是一个堆，现在我希望直接给一个数组，然后通过函数来将它变成一个堆。
这里有两种方法：
4.1向上调整建堆
//向上调整
static void AdjustUp(HPDataType* a, int children)
//从children对应的节点一直到最上面这一块进行调整
{assert(a);//先找到父节点和子节点的位置int parent = (children - 1) / 2;while (children > 0){//比较if (a[children] > a[parent]){Swap(&a[children], &a[parent]);//更新两个变量的值，让他们指向更新后的父节点，子节点children = parent;parent = (children - 1) / 2;}//如果发现比较结果不一样说明此时已经完成调整直接返回else{break;}}
}
//向上建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}
假设我们现在有一个数组：
这显然不是一个堆，但是如何调整呢？先回想一下刚才写的插入函数，在插入之前那个数组本身就是一个堆，插入之后通过向上调整仍然是个堆。
也就是说一个数组在用向上调整这个函数之前它本身就应该是一个堆，所以现在我们先不看数组的其它元素，只看这个数组的第一个元素，因为此时只有一个节点，本身就可以看做出一个堆。
然后在看前两个元素：
假设我们希望建一个大堆，那目前为止还符合我们的需求，继续往后看，发现到这里的时候，已经不是堆了，所以现在我们要通过向上调整来将它变成一个堆。
我们要调整的这一块内容：
将此时的27当成子节点，然后通过与其父节点作比较，一直到最后：
同样的道理，后面没多看一个元素，都进行一次比较，直到将整个数组都遍历完。这样就可以将一个数组变成了一个堆了。
现在我们分析一下向上调整建堆的时间复杂度：
假设这个数组高度为h。我们希望把这个二叉树变成一个堆，首先看第一行，第一行无论如何都可以不用动。
然后紧接从第二行开始，假设我们运气不好，每一行每添加一个元素都要进行一次挪动，总共2 ^ (h-1)个元素一个元素向上挪动(h-1)次
所以总次数可以这样写：
我们可以稍微计算一下：
因为算的是时间复杂度，所以这里不用算的太细，约一下就行结果就是：
2^hh+2
约一下就变成了2^hh
但是高度h和总结点个数N也有关系：
N = 2 ^ h - 1
h = log(N+1)(以2为底)
2^hh == (N+1) * log(N+1)
再约一下的时间复杂度结果就是Nlog(N)了这里的log都是以2为底，因为我打不出来所以就这样表示了。
4.2向下调整建堆
//向下调整
static void AdjustDown(HPDataType* a, int n, int parent)
//从此时父节点一直到末尾这一块结束
{assert(a);//假设左孩子最大int child = parent * 2 + 1;while(child < n){if (child + 1 < n && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
for (int i = ((n - 1) - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}
向下调整建堆还是之前那个数组：
向上调整的前提是调整前后都要保证是一个堆，而向下调整的前提是左右两个子树要保证是一个堆。我们通过上图可以看到，只有叶节点它的左右子树是空，也可以说叶节点本身可以看成一个堆。所以我们要从最后一个不是叶节点的地方也就是28的位置开始进行调整：
将这个地方当成需要调整的树，然后进行向下调整：
像这样将一个树分成一个一个子树进行向下调整。
这样规律就找出来了从节点28这里开始向下调整，然后父节点变成18，19，15…这样子将父节点的这个下标没调完一次向前跳一步，这样就能把所有的都搞好了。
然后现在我们再来算一下向下调整建堆的时间复杂度：
我们希望将这个二叉树变成一个堆，因为刚才分析过，叶子节点本身就可以当成一个堆，所以不需要进行调整，应该从倒数第二行的最后一个节点开始向下进行调整。
通过观察
发现倒数第二行最差的情况是要调整一次才能调完，倒数第三行是2次…这样就可以把式子列出来了：
然后进行化简最后结果：
又因为
h = log(N+1)(以2为底)
N = 2 ^ h - 1
可以约分成：
当N非常大的时候起始log(N+1)小，所以再算时间复杂度的时候这一块可以约去，所以时间复杂度是O(N).
同样是调整为什么向下调整建堆要比向上调整建堆要快呢？我们可以看一下向上调整建堆方法是从下向上的。
而且越往底节点个数越多，需要调整的次数越多。
再看向下调整建堆
这是从上向下的，倒数第二层的节点虽然是最多的，但发现它只用调整一次就够了。就是因为这样的一个差距才导致向下调整建堆要比向上调整建堆要快很多。
五.排序
5.1升序
我们刚才通过向下调整已经建好了一个堆，现在希望可以通过某些方法将这个堆变成一个有序数组。
如果是升序，我们可以建一个大堆：
//向下调整
static void AdjustDown(HPDataType* a, int n, int parent)
//从此时父节点一直到末尾这一块结束
{assert(a);//假设左孩子最大int child = parent * 2 + 1;while(child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//建堆并排序
void HeapSort(HPDataType* a, int n)
{//向下调整建堆for (int i = ((n - 1) - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//排序//升序要用大堆//先将最大的移到最后，然后向下调整int end = n - 1;while(end > 0)//当end等于1的时候说明此时就剩第一个元素此时就不需要调整了{//交换Swap(&a[0], &a[end]);//向下调整,从第一个元素开始一直向下调整到倒数第二个元素//从0一直到倒数第二个元素总共n-1个元素所以函数里放n-1也就是endAdjustDown(a, end, 0);//调整完一次循环开始向下调整从头到倒数第三个end--;}//调整for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
为什么升序要建一个大堆呢？如果我们建了一个小堆：
虽然堆顶的元素是最小值，但是找第二小的就会变得很麻烦，当然也可以将此时堆顶元素取出来存到一个新开辟的数组里，然后将剩下的重新建堆在取第二个…可以做倒是很麻烦不推荐。
所以这里我们建一个大堆：
我们将堆顶元素与最后一个互换，虽然我们不知道第二个，第三个哪个大，但是堆顶元素永远是最大的：
互换完成之后，我们在向下调整(但是我们现在直接忽略掉最后一个节点)：
现在就可以看到原来第二大的现在跑到堆顶上去了，像这样一直换一直调整，最后就可以把堆排序好了。
时间复杂度也可以算一下：
因为最后一行节点要比前面所有节点加起来还要多1，而且堆顶移动到堆底的次数也是最多的，所以算时间复杂度只算最后一行起始也是可以的：2 ^ (h - 1) * h然后约一下。
最后时间复杂度就是N*(logN).
5.2降序
建大堆是升序，建小堆就是降序。
六.TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决。
加入现在有一个10亿多的数，现在要求找到它的前5个大的数。因为10个数字确实非常大，一个数字是4字节，大约要用40G的空间，所以现在我们可以先将这么多数放到磁盘当中，而不是内存里，然后在内存里取前5个数来建一个小堆。这样的话，从这10亿个数里从第6个数开始，如果比堆顶数字大就替换，然后向下调整。这样一直向后遍历最终将前5个大的数找出来。
这里如果要取前5个最大的数一定要建小堆，如果你建了一个大堆，恰好第一个数是最大的数挡在堆顶这里，后面你不管什么数都进不来，所以导致得不到我们需要的内容。
//TOP-K问题
void TOP_K(int k)
{//定义k个大小的数组int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("TOP_K");exit(-1);}//在工程里新加一个文件FILE* fout = fopen("TOP_K.txt", "r");if (fout == NULL){perror("fopen");exit(-1);}//将文件里的前k个数读到数组里去for(int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//建小堆for (int i = ((k - 1) - 1) / 2; i >= 0; i--){AdjustDown(minHeap, k, i);}int val = 0;while (fscanf(fout, "%d", &val) != EOF){if (val > minHeap[0])//进堆然后向下调整{minHeap[0] = val;AdjustDown(minHeap, k, 0);}}//打印for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}free(minHeap);
}
这是我新建的一个.txt的文件，从里面读取数据并且进行排序
这样就把很多数据里的前5个大的数据选出来。