目录
一、堆
二、堆的模拟实现
1.结构体
2.push
3.pop和top
三.实现堆排序
1.成堆算法
2.堆排序
一、堆
分为大堆和小堆
大堆是每个父节点都大于子节点，小堆则相反是每个父节点都小于子节点
底层抽象结构是完全二叉树，下面实现方式底层是数组
二、堆的模拟实现
1.结构体
typedef int hptype;typedef struct heap
{hptype* data;int size;int capacity;}hp;void hpinit(hp* x)
{assert(x);x->data = NULL;x->capacity = x->size = 0;}void hpdestory(hp* x)
{assert(x);free(x->data);x->data = NULL;x->capacity = x->size = 0;}上面的typedef是为了方便改动
2.push
void swap(hptype* p1, hptype* p2)
{hptype tmp = *p1;*p1 = *p2;*p2 = tmp;}//把底下不符合堆的进行调整
//小堆
void adjustup(hptype* data, int child)
{assert(data);int parent = (child - 1) / 2;while (child > 0){if (data[child] < data[parent]){swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else { break; }}}
void hppush(hp* p, hptype x)
{assert(p);if (p->capacity == p->size){int num = p->capacity == 0 ? 4 : p->capacity * 2;hptype* newdata = (hptype*)realloc(p->data, sizeof(hptype) * num);if (newdata == NULL){perror("newdata==null");return;}p->data = newdata;p->capacity = num;}p->data[p->size++] = x;adjustup(p->data, p->size - 1);}
3.pop和top
void adjustdown(hptype* data, int size, int parent)
{assert(data);int small = parent * 2 + 1;while (small < size)
{ if(small+1<size&&data[small]>data[small+1]){small++;}if (data[parent] > data[small]){swap(&data[parent], &data[small]);parent = small;small = parent * 2 + 1;}else { break; }}}
void hppop(hp* x)
{assert(x);assert(x->size > 0);swap(&x->data[0], &x->data[x->size - 1]);x->size--;adjustdown(x->data, x->size, 0);}hptype hptop(hp*x)
{assert(x);return x->data[0];
}bool hpempty(hp*x)
{assert(x);return x->size == 0;
}pop是实现的把堆顶pop,还要保持堆的形象
应用：实现top_k个最小数的打印
思路：先将数据建堆，在获取top后pop，循环k次
void test2()
{int a[] = { 10,2,99,4,5,9,7,8,6, };hp x;hpinit(&x);for (int i=0;i<9;i++){hppush(&x, a[i]);}int k = 0;scanf("%d", &k);while(k--){printf("%d ", hptop(&x));hppop(&x);}}
三.实现堆排序
1.成堆算法
1.adjustup+for;
2.adjustdown+for
实例逻辑是小堆
void adjustup(hptype* data, int child)
{assert(data);int parent = (child - 1) / 2;while (child > 0){if (data[child] < data[parent]){swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else { break; }}}void adjustdown(hptype* data, int size, int parent)
{assert(data);int small = parent * 2 + 1;while (small < size)
{ if(small+1<size&&data[small]>data[small+1]){small++;}if (data[parent] > data[small]){swap(&data[parent], &data[small]);parent = small;small = parent * 2 + 1;}else { break; }}}for正序遍历+adjustup,时间复杂度 nlogn
void test3(){int a[10] = { 2,3,1,5,6,7,0,39,99,33 };for(int i=1;i<10;i++){adjustup(a, i);}for(int i=0;i<10;i++){printf("%d ", a[i]);}} 
for从叶子节点的父节点遍历+adjustdown
void test4() {int a[10] = { 2,3,1,5,6,7,0,39,99,33 };for (int i = (10-1-1)/2;i >=0;i--){adjustdown(a, 10,i);}for (int i = 0;i < 10;i++){printf("%d ", a[i]);}}
*调整算法复杂度讨论
adjustup+for
adjustdown+for
2.堆排序
底层思想是先成堆，在取堆顶数与末尾交换，即此时末尾一定是最大或最小，再以此类推
void heapsort(hptype *x,int n)
{assert(x);for(int i=1;i<n;i++){adjustup(x, i);}int end = n - 1;while(end>0){swap(&x[0], &x[end]);adjustdown(x, end, 0);end--;}}堆排序的升降是由堆是大小堆决定的，如果建成大堆，那么顶就是最大，取到队尾就是升序
如果小堆，取到队尾就是降序
升序=>大堆
降序=>小堆
*堆排序中while+adjustdown复杂度
四.*topk问题
求一堆数据中最大的前k个，这k个返回时不需要之间大小排序
思路1：直接对数据建大堆，顶上为最大，接着pop+top继续
时间复杂度：建堆O（n）+pop_topO( k*log(N) ) =>O（n）
空间复杂度：建堆O（n）
思路2：建k小堆，比顶上大的就顶上交换，然后再调整堆，以此类推
时间复杂度：建堆O（K）+遍历O(N-K) =>O( n )
空间复杂度：O(K)
void topk()
{int k = 0;scanf("%d", &k);int* kmax = (int*)malloc(k * sizeof(int));FILE* fout = fopen("data.txt", "r");//先取k个数进行建堆for(int i=0;i<k;i++){fscanf(fout, "%d", &kmax[i]);}for(int i=(k-1-1)/2;i>=0;i--){adjustdown(kmax, k, i);}int x = 0;
//打开文件开始遍历比较while(fscanf(fout,"%d",&x)>0){if(x>kmax[0]){kmax[0] = x;adjustdown(kmax, k, 0);}}//打印for(int i=0;i<k;i++){printf("%d ", kmax[i]);}}
