- //借助堆,查找最小的k个数
- #include <iostream>
- #include <assert.h>
- using namespace std;
- void maxheap(int heap[], int i, int len);
- /*-------------------
- build-min-heap(a)
- 1 heap-size[a] ← length[a]
- 2 for i ← |_length[a]/2_| downto 1
- 3 do max-heapify(a, i)
- */
- // 建立大根堆
- void buildheap(int heap[], int len)
- {
- if (heap == null)
- return;
- int index = len / 2;
- for (int i = index; i >= 1; i--)
- maxheap(heap, i, len);
- }
- /*----------------------------
- parent(i)
- return |_i/2_|
- left(i)
- return 2i
- right(i)
- return 2i + 1
- min-heapify(a, i)
- 1 l ← left(i)
- 2 r ← right(i)
- 3 if l ≤ heap-size[a] and a[l] < a[i]
- 4 then smallest ← l
- 5 else smallest ← i
- 6 if r ≤ heap-size[a] and a[r] < a[smallest]
- 7 then smallest ← r
- 8 if smallest ≠ i
- 9 then exchange a[i] <-> a[smallest]
- 10 min-heapify(a, smallest)
- */
- //调整大根堆
- void maxheap(int heap[], int i, int len)
- {
- int largeindex = -1;
- int left = i * 2;
- int right = i * 2 + 1;
- if (left <= len && heap[left] > heap[i])
- largeindex = left;
- else
- largeindex = i;
- if (right <= len && heap[right] > heap[largeindex])
- largeindex = right;
- if (largeindex != i)
- {
- swap(heap[i], heap[largeindex]);
- maxheap(heap, largeindex, len);
- }
- }
- int main()
- {
- // 定义数组存储堆元素
- int k;
- cin >> k;
- int *heap = new int [k+1]; //注,只需申请存储k个数的数组
- file *fp = fopen("data.txt", "r"); //从文件导入海量数据(便于测试,只截取了9m的数据大小)
- assert(fp);
- for (int i = 1; i <= k; i++)
- fscanf(fp, "%d ", &heap[i]);
- buildheap(heap, k); //建堆
- int newdata;
- while (fscanf(fp, "%d", &newdata) != eof)
- {
- if (newdata < heap[1]) //如果遇到比堆顶元素kmax更小的,则更新堆
- {
- heap[1] = newdata;
- maxheap(heap, 1, k); //调整堆
- }
- }
- for (int j = 1; j <= k; j++)
- cout << heap[j] << " ";
- cout << endl;
- fclose(fp);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/221020136566.html
来源: http://www.codesnippet.cn/detail/221020136566.html