【什么是堆】
概念：堆是一种特殊的二叉树，具备以下两种性质
1）每个节点的值都大于（或者都小于，称为最小堆）其子节点的值
2）树是完全平衡的，并且最后一层的树叶都在最左边
这样就定义了一个最大堆。如下图用一个数组来表示堆：
那么下面介绍二叉堆：二叉堆是一种完全二叉树，其任意子树的左右节点（如果有的话）的键值一定比根节点大，上图其实就是一个二叉堆。
你一定发觉了，最小的一个元素就是数组第一个元素，那么二叉堆这种有序队列如何入队呢？看图：
假设要在这个二叉堆里入队一个单元，键值为2，那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复杂度为Ο(logn)的操作，二叉堆还是二叉堆。
那如何出队呢？也不难，看图：
出队一定是出数组的第一个元素，这么来第一个元素以前的位置就成了空位，我们需要把这个空位挪至叶子节点，然后把数组最后一个元素插入这个空位，把这个“空位”尽量往上挪。这种操作的复杂度也是Ο(logn)。
【适用范围】
海量数据前n大，并且n比较小，堆可以放入内存
【基本原理及要点】
最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元 素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。
【扩展】
双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。
【问题实例】
1)100w个数中找最大的前100个数。
当前标签: 海量数据
海量数据处理专题（五）——堆（百度，搜狗，雅虎，微软面试必备） 码农1946 2012-08-28 19:35 阅读:593 评论:1
海量数据处理专题（四）——Bit-map 码农1946 2012-08-28 08:27 阅读:484 评论:2
海量数据处理专题（三）——Hash 码农1946 2012-08-23 20:11 阅读:1614 评论:0
海量数据处理专题（八）——倒排索引(搜索引擎之基石) 码农1946 2011-09-26 01:06 阅读:3049 评论:9
海量数据处理专题（二）——Bloom Filter 码农1946 2011-08-29 00:43 阅读:2978 评论:2
海量数据处理专题（七）——数据库索引及优化 码农1946 2011-08-17 23:49 阅读:5325 评论:11
海量数据处理专题（一）面试百度，腾讯，雅虎。。的利器 码农1946 2010-10-02 14:17 阅读:24654 评论:18