一、堆的概念及结构
二、 向上调整算法
注意:循环条件不可写parent > 0
//向上调整算法
//child为下标
void adjustup(int* 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;}}
}三、向下调整算法
他的时间复杂度比向上调整算法要更低,因此尽可能用向下调整算法
//向下调整算法
//n为数据个数,parent为下标
void adjustdown(int* a, int n, int parent)
{int child = parent * 2 + 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 = parent * 2 + 1;;}else{break;}}
}四、完整的堆的实现
Heap.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<stdbool.h>//小堆
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
heap.c
#include"Heap.h"void HeapInit(Heap* hp)
{assert(hp);hp->_a = NULL;hp->_capacity = 0;hp->_size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp->_a);hp->_a = NULL;hp->_capacity = 0;hp->_size = 0;
}// 堆的判空
bool HeapEmpty(Heap* hp)
{assert(hp);return 0 == hp->_size;
}
void swap(HPDataType* p1, HPDataType* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//向上调整算法
//child为下标
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;}}
}
//向下调整算法
//n为数据个数,parent为下标
void adjustdown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 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 = parent * 2 + 1;;}else{break;}}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->_capacity == hp->_size){int newcapacity = (hp->_capacity == 0 ? 4 : hp->_capacity * 2);HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);if(NULL == tmp){perror("HeapPush realloc fail!!");return;}hp->_a = tmp;hp->_capacity = newcapacity;}hp->_a[hp->_size] = x;hp->_size++;adjustup(hp->_a, hp->_size - 1);
}
// 堆的删除,指删除顶部数据
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));swap(&hp->_a[0], &hp->_a[hp->_size - 1]);hp->_size--;adjustdown(hp->_a, hp->_size, 0);}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp->_size;
}heaptest.c
#include"Heap.h"void test()
{Heap hpp;HeapInit(&hpp);int aa[] = { 65,100,70,32,50,60 };for (int i = 0; i < sizeof(aa) / sizeof(int); ++i){HeapPush(&hpp, aa[i]);}while(!HeapEmpty(&hpp)){int top = HeapTop(&hpp);printf("%d\n", top);HeapPop(&hpp);}HeapDestory(&hpp);
}
typedef int datatype;
//利用向上调整建堆
//n为元素个数
void CreatHeapByadjustup(datatype* a, int n)
{int i = 0;for (i = 1; i< n; i++){adjustup(a, i);}
}
//利用向下调整建堆
// 他的时间复杂度更低
//n为元素个数
void CreatHeapByadjustdown(datatype* a, int n)
{int i = 0;//叶子结点无法下调整,所以传入最后一个父亲//最后一个父亲等于元素个数(n - 1 - 1) / 2for (i = (n - 2) / 2; i >= 0; i--){adjustdown(a, n, i);}
}
//堆排序
//n为元素个数
void HeapSort(datatype* a, int n)
{//利用向下调整建堆CreatHeapByadjustdown(a, n);int end = n - 1;while (end){swap(&a[0], &a[end]);end--;//将数组第一个元素放到合适位置,重新变为堆adjustdown(a, end, 0);}
}
//int main()
//{
// //test();
// //利用向上调整建堆
// //int aa[] = { 65,100,70,32,50,60 };
// //利用向上调整建堆
// //CreatHeapByadjustup(aa, sizeof(aa) / sizeof(int));
// //利用向下调整建堆
// //CreatHeapByadjustdown(aa, sizeof(aa) / sizeof(int));
// //堆排序,
// //想要获得降序,就要建立小堆
// //因为建立小堆可以取出最小的值放到数组尾部,然后再建小堆,
// //同样想要获得降升序,就要建立大堆
// //HeapSort(aa, sizeof(aa) / sizeof(int));
//
//
// return 0;
//}五、堆排序
想要获得降序,就要建立小堆,因为建立小堆可以取出最小的值放到数组尾部,然后再建小堆,同样想要获得降升序,就要建立大堆
//利用向上调整建堆
//n为元素个数
void CreatHeapByadjustup(datatype* a, int n)
{int i = 0;for (i = 1; i< n; i++){adjustup(a, i);}
}
//利用向下调整建堆
// 他的时间度更低
//n为元素个数
void CreatHeapByadjustdown(datatype* a, int n)
{int i = 0;//叶子结点无法下调整,所以传入最后一个父亲//最后一个父亲等于元素个数(n - 1 - 1) / 2for (i = (n - 2) / 2; i >= 0; i--){adjustdown(a, n, i);}
}
//堆排序
//n为元素个数
void HeapSort(datatype* a, int n)
{//利用向下调整建堆CreatHeapByadjustdown(a, n);int end = n - 1;while (end){swap(&a[0], &a[end]);end--;//将数组第一个元素放到合适位置,重新变为堆adjustdown(a, end, 0);}
}
int main()
{test();//利用向上调整建堆int aa[] = { 65,100,70,32,50,60 };//利用向上调整建堆CreatHeapByadjustup(aa, sizeof(aa) / sizeof(int));//利用向下调整建堆CreatHeapByadjustdown(aa, sizeof(aa) / sizeof(int));//堆排序,//想要获得降序,就要建立小堆//因为建立小堆可以取出最小的值放到数组尾部,然后再建小堆,//同样想要获得降升序,就要建立大堆HeapSort(aa, sizeof(aa) / sizeof(int));return 0;
}六、Top-K 问题
Top-k问题:
假设有10万亿数据,取k个最大的.数据量很大,就不可以把数都存进去,因为存储空间不允许
解决思路:那么我们就开辟K个空间的数组,插入K个数据建小堆, 然后再插入就和堆中最小数(数组第一个数)进行比较,堆中最小数比较小,就插入代替他,利用堆排序,重新将鼠标变为堆,当遍历完所有数据,数组中存放的就是最大的K个数字
注:adjustdown()函数在前面堆的实现有
/为了方便直接观察,我们可以创造数据
void CreateNDate()
{// 造数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void PrintTopK(int k)
{const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc error");return;}//读取前k个数据for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}// 将10个数据建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){adjustdown(kminheap, k, i);}//之后的插入int val = 0;while (!feof(fout)){fscanf(fout, "%d", &val);if (val > kminheap[0]){kminheap[0] = val;adjustdown(kminheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");
}
int main()
{//创造第一次之后,就注释,//然后打开文件手动将4个数改为最大的再次运行CreateNDate();PrintTopK(5);return 0;
}
