《海量数据查找中位数》由会员分享，可在线阅读，更多相关《海量数据查找中位数（5页珍藏版）》请在金锄头文库上搜索。
1、若有很大一组数据，数据的个数是N(每个数占4 个字节 ),内存大小为M 个字节 ,其中 MN/2 那一个计数器， 它所代表的数就是这N 个数的中位数。2. 题目是这样的，给定一个集合，首先该集合为空，之后不断往集合中加入整数，请依 次输出每次加入一个整数后，集合里的中位数，请给出你的算法。如下面的例子集合 中位数1 1 1,2 1 1,2,4 2 1,2,4,7 2 1,2,4,7,13 4刚开始就想到平衡二叉树，红黑树，因为听 defense 说平衡二叉树就是保持左右字数的节 点数量差不大于 1，那经过构造处理，树的根元素肯定就是中位数了。但碍于平衡二叉树 没细看过，就先空着了。由于最近几天
2、一直关注着堆排序，而且进攻老提起他面试笔试的时候碰到算法题要用堆，脑子里也老是堆在那打转。还别说，真的是突然灵光一现，想到 了用一个最小堆和一个最大堆来实现，而且思路也很清晰，处理起来也很简单。就是保持 最大堆的堆顶元素小于最小堆的堆顶元素，并且最大堆和最小堆的节点数量差不超过 1。 这样每次来一个新的元素，只要插入到其中一个堆中就可以了。如果来得元素是在节点数 多的堆，则取出堆顶元素放到另一个堆中，再插入。这样处理起来就很清楚了。在用代码实现的时候，始终保持最大堆比最小堆元素多 1 个，或者相等。例如，1-4-2 是最大堆，13-7 是最小堆，下一个数是 3，则把 4 放到最小堆，3 放入最
3、大堆， 这种最坏情况下的复杂度是2*lg(n/2),如果运气好的话，只是简单插入的话，就是 lg(n/2)了。自己感觉这个方法操作上简单，理解上也很容易，代码实现上几乎没什么要写的，只需要 把数据结构书中的最小堆程序 copy 一下，简单处理就 ok 了。如果有达人提出更好的算法， 还肯告知。下面给出我写的程序（比较垃圾，凑合着看吧），最小堆和最大堆都是用数组存储的，数 组 0 位置是堆顶，1 是左节点，2 是右节点，3 就是 1 的左节点。k 是 2k+1 和 2k+2 的根节 点。#include #define MAX 10 /所有用来找中位数的数字都大于 0 小于 1024，输入 0
4、结束查找int MinHeapMAX=1024; int MaxHeapMAX=0;int min=0; int max=0;int GetMaxHeap(); void InsertMaxHeap(int m); void OverInsertMaxHeap(int m);int GetMinHeap(); void InsertMinHeap(int m); void OverInsertMinHeap(int m);int main(void) int m;while (1) scanf(“%d“,if (!m) break;if (max = min) if (GetMinHeap()
5、=m) InsertMaxHeap(m);elseInsertMaxHeap(GetMinHeap();OverInsertMinHeap(m);elseif (GetMaxHeap()0) if (m MinHeapchild) MinHeapcurrent=MinHeapchild;current=child;child=current*2+1;elsebreak;MinHeapcurrent=m; int GetMaxHeap() return MaxHeap0; void InsertMaxHeap(int m) int parent=(max-1)/2;int current=max
6、;while (current0) if (m MaxHeapparent) MaxHeapcurrent = MaxHeapparent;current = parent;parent =(current-1)/2; elsebreak;MaxHeapcurrent = m;max+; void OverInsertMaxHeap(int m) int current=0;int child=current*2+1;while (child MaxHeapchild) child+;if (m MaxHeapchild) MaxHeapcurrent=MaxHeapchild;current=child;child=current*2+1;elsebreak;MaxHeapcurrent=m;
