想做网站,湖南省公司注册网站,网站建设 图片上传,网页游戏网游目录 一 降序(建小堆)
二 升序 (建大堆)
三 优化(以升序为例)
四 TOP-K问题 一 降序(建小堆)
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//降序 建小堆
void AdjustUp(int* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[chil…目录 一 降序(建小堆)
二 升序 (建大堆)
三 优化(以升序为例)
四 TOP-K问题 一 降序(建小堆)
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//降序 建小堆
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;}}
}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;}}
}void HeapSort(int* a, int n)
{int end n - 1;int i 0;//建堆for (i 1; i n; i){AdjustUp(a, i);}while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}int main()
{int a[] { 2, 3, 5, 7, 4, 6, 8 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
} 二 升序 (建大堆)
//升序 建大堆
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;}}
}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;}}
}void HeapSort(int* a, int n)
{int end n - 1;int i 0;//建堆for (i 1; i n; i){AdjustUp(a, i);}while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}int main()
{int a[] { 2, 3, 5, 7, 4, 6, 8 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
} 三 优化(以升序为例)
可以用向下建堆的方法
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;}}
}//void HeapSort(int* a, int n)
//{
// int end n - 1;
// int i 0;
// //建堆
// for (i 0; i n; i)
// {
// AdjustUp(a, i);
// }
//
// while (end 0)
// {
// Swap(a[0], a[end]);
// AdjustDown(a, end, 0);
// end--;
// }
//}void HeapSort(int* a, int n)
{int end n - 1;int i 0;//建大堆for (i (n-1-1) / 2; i 0; i--){AdjustDown(a, n, i);}while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
int main()
{int a[] { 2, 3, 5, 7, 4, 6, 8, 65, 100, 70, 32, 50, 60};HeapSort(a, sizeof(a) / sizeof(int));return 0;
} 这样建堆的方式对时间复杂度有什么优化吗? 四 TOP-K问题
TOP - K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。
比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top - K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下1. 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆
2. 用剩余的N - K个元素依次与堆顶元素来比较不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
#includestdio.h
#includestdlib.h
#includetime.htypedef int HPDataType;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}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 PrintTopK(const char* filename, int k)
{//1 建堆--用a中前K个元素建堆(小堆)FILE* fout fopen(filename, r);if (fout NULL){perror(fopen fail);return;}int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(malloc fail);return;}for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);}//前K个建小堆for (int i (k-2) / 2; i 0; i--){AdjustDown(minheap, k, i);}//2 将剩余n-k元素与堆顶元素比较, 满足就交换int x 0;while (fscanf(fout, %d, x) ! EOF){if (x minheap[0]){//替换进堆minheap[0] x;AdjustDown(minheap, k, 0);}}for (int i 0; i k; i){printf(%d , minheap[i]);}printf(\n);fclose(fout);}void CreateDate()
{//造数据int n 100000;srand(time(0));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen error);return;}for (int i 0; i n; i){int x (rand() i) % n;fprintf(fin, %d\n, x);}fclose(fin);
}int main()
{CreateDate();PrintTopK(data.txt, 5);return 0;
} 本节对前面的二叉树基础很高, 没有理解的, 可以翻看我之前对二叉树顺序结构及其实现的章节.
继续加油!
