首页 > 代码库 > 一个堆排序问题
一个堆排序问题
题目：在N个不相等的整数中找出最大的第K个数(N>K)。
思路：首先，用前K个整数构造容量为K的最小堆。然后，将后N-K个整数依次与堆顶元素比较，若比堆顶元素大，则替换堆顶元素并调整最小堆结构；反之，则继续比较下一个整数。最终，最小堆存储最大的k个数，其堆顶元素即为所求。
代码：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <ctime> 5 #include <iostream> 6 7 #define N 90 8 #define K 13 9 10 11 void HeapAdjust (int *heap, int beginidx, int endidx); 12 void HeapConstruct (int *heap); 13 14 void SetData (int *data); 15 void ShowData (int *data); 16 17 int main (int argc, char **argv) 18 { 19 int i; 20 int h[N + 1]; 21 22 SetData(h); 23 ShowData(h); 24 25 HeapConstruct(h); 26 for (i = K + 1; i <= N; i++) 27 { 28 if (h[i] > h[1]) 29 { 30 h[1] = h[i]; 31 HeapAdjust(h, 1, K); 32 } 33 } 34 35 printf("The Kth biggest number: %d\n", h[1]); 36 return 0; 37 } 38 39 void HeapAdjust (int *heap, int beginidx, int endidx) 40 { 41 int ¤t = beginidx; 42 int tmp, left, right, data =http://www.mamicode.com/ heap[current]; 43 44 while (left = (current << 1), left <= endidx) 45 { 46 right = left | 1; 47 if ((left == endidx) || (heap[left] < heap[right])) 48 { 49 tmp = left; 50 } 51 else 52 { 53 tmp = right; 54 } 55 if (data > heap[tmp]) 56 { 57 heap[current] = heap[tmp]; 58 current = tmp; 59 } 60 else 61 { 62 break; 63 } 64 } 65 heap[current] = data; 66 } 67 68 void HeapConstruct (int *heap) 69 { 70 int i; 71 for (i = K/2; i > 0; i--) 72 { 73 HeapAdjust(heap, i, K); 74 } 75 } 76 77 void SetData (int *data) 78 { 79 bool *bdata = http://www.mamicode.com/new bool[N + 1]; 80 memset(bdata, false, N + 1); 81 srand(time(NULL)); 82 data[0] = -1; 83 for (int i = 1; i <= N; i++) 84 { 85 data[i] = rand() % N + 1; 86 while (bdata[data[i]]) 87 { 88 data[i] = rand() % N + 1; 89 } 90 bdata[data[i]] = true; 91 } 92 delete []bdata; 93 } 94 95 void ShowData (int *data) 96 { 97 for (int i = 1; i <= N; i++) 98 { 99 printf("%02d ", data[i]);100 }101 puts("");102 }
时间复杂度：(N-K+1)*K*lgK.
一个堆排序问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。