2022年2022年海量数据查找中位数 .pdf

若 有 很 大 一 组 数 据 ，数 据 的 个 数 是 N( 每 个 数 占4 个 字 节 ), 内 存 大 小 为M个 字 节 ,其 中 M 4 * N, 使 得 不 能 在 现 有 内 存 情 况 下 通 过 直 接 排 序 找 到 这N个 数 的 中 位 数 。解 决 海 量 数 据 中 取 中 位 数 的 方 法 有 两 种 比 较 简 单 耗 时 的是 用 堆 排 序 ,还 有 一 种 是 改 造 后 基 于 段 的 计 数 :1 ） 分 区 间 堆 排 序 ： 在 现 有M 大 小 内 存 情 况 下 若 最 多 能 够 造 出 包 含p 个数 据 的 堆 ， 则 先 扫 描 一 次 这N个 数 据 找 到 最 小 的p个 数 ， 耗 时O ( Nl og ( p ) ) ， 设 这p 个 数 中 最 大 的 数 是a , 将 堆 清 空 ， 在 第 二 轮 扫 描出 比 a 大 的 中 最 小 的 p 个 数 ， 然 后 在 把 a 改 为 记 录 这p 个 数 中 最 大的 数 ， 依 次 类 推 ， 直 到 计 算 到 某 一 轮p 个 数 和 之 前 够 造 出 的 数 的 个数 大 于 N/ 2 ， 在 这p 个 数 中 找 到 所 有 数 中 的 中 位 数 ,耗 时 的 地 方 是 每轮 扫 描 构 建 堆 都 要 用 了O ( Nl o g ( p ) ) , 构 造 的 次 数 为N/ (2 *p ) ， 所 以 它的 时 间 复 杂 度 是O ( N* N*l o g ( p) / (2 *p ) ). 2) 基 于 段 的 计 数基 于 段 的 计 数 指 的 的 是 对 一 个 区 间 范 围 的 计 数 ， 与 计 数 排 序 不 同 的是 后 者 对 每 一 个 数 出 现 次 数 的 计 数 ， 而 前 者 是 对 出 现 在 某 一 区 间 范围 内 的 数 计 数 ， 段 的 大 小 取 决 于 内 存 大 小 和 每 段 计 数 器 所 占 的 字 节数 ， 而 计 数 器 大 小 又 受 总 数 据 量 有 关 ， 需 满 足 计 数 器 的 最 大 计 数 能够 大 于 最 大 个 数N， 比 如 本 题 中 内 存 大 小 是M 个 字 节 ， 而N 的 大 小至 少 需 要 用l o gN 位 来 表 示 ，设k 个 字 节 表 示 的 无 符 号 整 数 可 以 最 大值 大 于 N，则 放 在 内 存 中 计 数 器 个 数 是 M/ k ,设q = M/ k , 即 这N 个 数 分为q 个 段 ， 每 一 段 的 大 小 是 n = N/ q ， 第 一 段 数 的 范 围 是 0 n -1 , 第 二段 是 n 2*n - 1 , 依 此 类 推 。 现 在 我 们 可 以 从 硬 盘 中 逐 个 扫 面 这 N 个 数 ，根 据 每 个 数 的 大 小 来 修 改 他 们 对 应 范 围 的 计 数 器 ，需 要 用 O (N) 时 间完 成 对 这q 个 段 的 计 数 。 然 后 从 第 一 段 开 始 往 后 扫 描 累 加 每 个 段 的计 数 器 ， 直 到 累 加 到 某 一 段 的 计 数 器 使 得 它 和 这 之 前 的 个 数 大 于 N/ 2 ，假 设 这 个 段 所 表 示 的 范 围 是q q + n -1 ， 那 么 这N 个 数 的 中 位 数 就 在q q + n -1 这 个 范 围 内 ,现 在 更 改 计 数 器 的 属 性 不 在 基 于 段 而 是 基 于 每个 数 ， 且 只 针 对q q +n - 1 这 n 个 数 计 数 ， 还 需 要 一 轮 扫 面N 个 数 来完 成 对n个 计 数 器 的 确 定 ， 在 本 段 之 前 的 段 计 数 器 计 数 之 和 是t, t N/ 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，那经过构造处理，树的根元素肯定就是中位数了。但碍于平衡二叉树没细看过， 就先空着了。 由于最近几天一直关注着堆排序，而且进攻老提起他面试笔试的时候碰名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 到算法题要用堆，脑子里也老是堆在那打转。还别说， 真的是突然灵光一现，想到了用一个最小堆和一个最大堆来实现，而且思路也很清晰，处理起来也很简单。就是保持最大堆的堆顶元素小于最小堆的堆顶元素，并且最大堆和最小堆的节点数量差不超过1。这样每次来一个新的元素， 只要插入到其中一个堆中就可以了。如果来得元素是在节点数多的堆，则取出堆顶元素放到另一个堆中，再插入。这样处理起来就很清楚了。在用代码实现的时候，始终保持最大堆比最小堆元素多1 个，或者相等。例如， 1-4-2 是最大堆， 13-7 是最小堆，下一个数是3，则把 4 放到最小堆， 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 结束查找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,&m); if (!m) break; if (max = min) if (GetMinHeap()=m) InsertMaxHeap(m); else InsertMaxHeap(GetMinHeap(); OverInsertMinHeap(m); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - else if (GetMaxHeap()0) if (m MinHeapparent) MinHeapcurrent = MinHeapparent; current = parent; parent = (current-1)/2; else break; MinHeapcurrent = m; min+; void OverInsertMinHeap(int m) int current=0; int child=current*2+1; while (child min) if (child+1min & MinHeapchild+1 MinHeapchild) MinHeapcurrent=MinHeapchild; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - current=child; child=current*2+1; else break; MinHeapcurrent=m; int GetMaxHeap() return MaxHeap0; void InsertMaxHeap(int m) int parent=(max-1)/2; int current=max; while (current0) if (m MaxHeapparent) MaxHeapcurrent = MaxHeapparent; current = parent; parent =(current-1)/2; else break; MaxHeapcurrent = m; max+; void OverInsertMaxHeap(int m) int current=0; int child=current*2+1; while (child max) if (child+1 MaxHeapchild) child+; if (m MaxHeapchild) MaxHeapcurrent=MaxHeapchild; current=child; child=current*2+1; else break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - MaxHeapcurrent=m; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -