网页制作与网站建设宝典（第2版）,建企业网站哪家好,淄博营销网站建设服务,wordpress怎么访问堆#xff1a;是一种特殊的完全二叉树#xff0c;一般通过顺序表存储#xff0c;分为大堆和小堆两类。
大堆#xff1a;父节点的值恒大于子节点的值。
小堆#xff1a;父节点的值恒小于子节点的值。
创建堆#xff0c;可以使得根节点成为整个堆中保存最大或最小的值的…堆是一种特殊的完全二叉树一般通过顺序表存储分为大堆和小堆两类。
大堆父节点的值恒大于子节点的值。
小堆父节点的值恒小于子节点的值。
创建堆可以使得根节点成为整个堆中保存最大或最小的值的结根据这个特性堆可以用于排序和解决TopK问题。 创建堆
方法一向上排序法
原理对由前k个结点构成的堆插入第k1个结点到最后然后不断与其父节点进行比对符合条件就互换不符合条件就留在原地结束循环。循环结束后前k1个结点仍是堆。 时间复杂度Onlogn 方法二向下排序
原理首先创造一个完全二叉树然后从倒数第二层最后一个结点开始不断以当前结点为根节点创建堆直至最后以根节点创建堆。每次创建堆都是先比较该结点的子节点找出更可能上移的结点然后与父节点比较符合条件就互换然后继续该步骤不符合条件就停止循环。循环结束后该部分就成为了一个堆。
时间复杂度ON 堆排序
思路将根节点与最后一个结点互换使得最后一个结点永远保存当前最大小的结点然后对互换后的根节点进行向下排序使得排完序列后整个二叉树仍然是堆再将新的根节点与倒数第二个结点互换重复上述操作。最后整个堆就是一个升序或降序的顺序表。
时间复杂度ONlogN
每个根节点最多移动logN次一共N-1个结点进行移动因此时间复杂度是NlogN。 具体代码实现
void swap1(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
void up_insert1(HPDataType* a, int i)
{int child i;int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){swap1(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}}
void down_insert1(HPDataType* a, int n, int i)
{int parent i;int child parent * 2 1;while (child n){if (child 1 n a[child] a[child 1]){child;}if (a[parent] a[child]){swap1(a[parent], a[child]);parent child;child child * 2 1;}else{break;}}}
void HeapSort(int* a, int n)
{//创建堆for (int i 1; i n; i){up_insert1(a, i);}测试//for (int i 0; i n; i)//{// printf(%d , a[i]);//}//printf(\n);//排序for (int i 0; i n; i){swap1(a[0], a[n - 1-i]);down_insert1(a, n - i - 1, 0);}//测试for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);} TopK问题
问题要求对N个数据只取最大或最小的前k个。
思路先用前k个数据创建堆此处要求取最大的前k个则创建小堆。
创建小堆后根元素为整个堆中最下的元素新的元素若比根节点大则替换根节点然后进行向下排序使得整个二叉树仍然为堆。进行N-k次上述操作得到的堆就会保存最大的前k个元素。
具体代码
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 swap1(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
void down_insert1(HPDataType* a, int n, int i)
{int parent i;int child parent * 2 1;while (child n){if (child 1 n a[child] a[child 1]){child;}if (a[parent] a[child]){swap1(a[parent], a[child]);parent child;child child * 2 1;}else{break;}}}
void PrintTopK(int k)
{const char* file data.txt;FILE* fin fopen(file, r);//创建小堆 (找最大的前k个)int* arr (int*)malloc(sizeof(int) * k);if (arr NULL){perror(malloc);exit(-1);}int i 0;int num k;while (num--){fscanf(fin, %d\n, arr[i]);i;}Heap hp;HeapCreate(hp, arr, k);//插入其余元素int x 0;int count 0;while (fscanf(fin, %d\n, x) ! EOF){ /* if (count % 1000 0){x * 1000;}*/if (x hp.a[0]){hp.a[0] x;down_insert1(hp.a, k, 0);}}printf(插入成功\n);//测试for (int j 0; j k; j){printf(%d ,hp.a[j]);}printf(\n);}
