目录
- 1.二叉树的顺序存储
- 2.堆的性质
- 3.堆的实现
- 3.1 堆的插入(向上调整算法)
- 3.2 堆向下调整算法
- 3.3 堆的创建
- 3.4 堆的删除
- 3.5 全套代码
- 4.堆排序
- 5.Top-K问题
1.二叉树的顺序存储
顺序存储就是数组存储,一般使用数组只适合完全二叉树,因为不是完全二叉树会有空间上的浪费。在现实生活中,只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
2.堆的性质
小堆
堆是一棵完全二叉树
堆的父亲节点总是小于孩子节点
根节点最小
大堆
堆是一棵完全二叉树
堆的父亲节点总是大于孩子节点
根节点最大
3.堆的实现
3.1 堆的插入(向上调整算法)
方法:
1.先将元素插入到堆的末尾,即最后一个孩子处
2.插入后如果堆的性质遭到破坏,将新插入节点顺着双亲往上调整时间复杂度:O(NlogN)
举例:先插入一个20
到堆的末尾,再往上进行调整算法,直到满足堆
举例:先插入一个10
到堆的末尾,再往上进行调整算法,直到满足堆
void Adjustup(HPDataType* a, int child)
{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;}}
}
3.2 堆向下调整算法
现在我们给出一个数组,逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
前提:左右子树必须是一个堆,才能调整
时间复杂度:O(N)
int a[]={27,15,19,18,28,34,65,49,25,37};
void AdjustDown(HPDataType* a, int n, int parent)
{//假设法:假设左孩子比右孩子小//求左孩子的下标int child = parent * 2 + 1;while (child<n){if (child + 1 < n && a[child] > a[child + 1])//左孩子比右孩子大{++child;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}
}
3.3 堆的创建
下面我们给一个数组,这个数组逻辑上可以看成一棵完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。
根节点左右子树不是堆,我们怎么调整呢?
方法一:向下调整法
我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的数,就可以调整成堆
方法二:向上调整算法
我们把数组第一个元素看成是堆,然后利用循环构建堆
int a[]={ 4,2,8,1,5,6,9,7,2,7,9 };
向下调整算法
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(a, n, i);
}
向上调整算法
for (int i = 1; i < n; i++)
{Adjustup(a, i);
}
3.4 堆的删除
删除堆是删除堆顶的数据,将堆顶的数据跟最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。
3.5 全套代码
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;void HPInint(Heap* hph);//初始化
void HPDestroy(Heap* hph);//销毁
void HPPush(Heap* hph, HPDataType x);//插入
void HPPop(Heap* hph);//删除
HPDataType HPTop(Heap* hph);//取堆顶元素
bool HPEmpty(Heap* hph);//判空
int HeapSize(Heap* hp);//求个数void Adjustup(HPDataType* a, int child);//向上调整算法
void swap(HPDataType* p1, HPDataType* p2);//交换
void AdjustDown(HPDataType* a, int n, int parent);//向下调整算法#include "Heap.h"void HPInint(Heap* hph)
{assert(hph);hph->a = NULL;hph->capacity = hph->size = 0;
}void HPDestroy(Heap* hph)
{assert(hph);free(hph->a);hph->a = NULL;hph->capacity = hph->size = 0;
}void swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//时间复杂度:NlogN
void Adjustup(HPDataType* a, int child)
{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)
{//求左孩子的下标int child = parent * 2 + 1;//假设法:while (child<n){if (child + 1 < n && a[child] > a[child + 1]){++child;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}
}void HPPush(Heap* hph, HPDataType x)
{assert(hph);//扩容if (hph->capacity == hph->size){int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(hph->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}//扩容成功hph->a = tmp;hph->capacity = newcapacity;}hph->a[hph->size] = x;hph->size++;//向上调整Adjustup(hph->a, hph->size - 1);
}void HPPop(Heap* hph)
{assert(hph);assert(hph->size > 0);swap(&hph->a[0], &hph->a[hph->size - 1]);hph->size--;//向下调整AdjustDown(hph->a, hph->size, 0);
}HPDataType HPTop(Heap* hph)
{assert(hph);assert(hph->size > 0);return hph->a[0];
}
bool HPEmpty(Heap* hph)
{assert(hph);return hph->size == 0;
}int HeapSize(Heap* hph)
{assert(hph);return hph->size;
}
4.堆排序
堆排序是利用堆积树这种结构所设计的一种排序的算法,它是选择排序的一种。
排升序建大堆
排降序建小堆
时间复杂度:O(Nlog N)
void HeapSort(int* a, int n)
{//建堆//升序,建大堆降序,建小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//建堆完成int end = n - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}
5.Top-K问题
求数据结合中前k个最大的元素或者最小的元素,一般情况下数据量都比较大。
eg:专业前10名,世界500强等
对于top-k问题,能想到最简单的问题就是排序,但是:如果数据量非常大,排序就不可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决
- 用数据集合中前k个元素建堆
- 前k个最大元素,建小堆
- 前k个最小元素,建大堆
- 用剩余的N-K个元素一次与堆顶元素相比较,不满足则替换堆顶元素
void PrintTopK(int* a, int n, int k)
{//升序,建大堆//降序,建小堆// 1. 建堆--用a中前k个元素建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则替换for (int i = k ; i < n; i++){if (a[i] > a[0]){a[0] = a[i];AdjustDown(a, k, 0);}}int end = k - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}//打印前k个最大的数for (int i = 0; i < 5; i++)printf("%d ", a[i]);
}