二分法

二分法又可以被称为二分查找，它描述了在有序集合中搜索特定值的过程。广义的二分查找是将问题的规模尽可能的缩小到原有的一半。

对于二分法的思想大家都能讲出几句，但我们仍然很难讲其与实际应用完美的结合到一起，所以我们尽量汇总二分法的应用场景，和大家一起深入，共勉！
一、常见问题
给定一个由数字组成的有序数组 nums，并给你一个数字 target。问 nums 中是否存在 target。如果存在，则返回其在 nums 中的索引。如果不存在，则返回 - 1。
这是二分查找中最简单的一种形式。当然二分查找也有很多的变形，这也是二分查找容易出错，难以掌握的原因。
常见变体有：

如果存在多个满足条件的元素，返回最左边满足条件的索引。
如果存在多个满足条件的元素，返回最右边满足条件的索引。
数组不是整体有序的。 比如先升序再降序，或者先降序再升序。
将一维数组变成二维数组…等等


二、二分查找中使用的术语
如前所述，二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。但要注意排序的成本

target: 要查找的值
index: 查找时的当前位置
left 和 right: 左右指针
mid: 左右指针的中点，用来确定我们应该向左查找还是向右查找的索引

在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。
注意：

二分法搜索可以采用许多替代形式
可能并不总是直接搜索特定值
你不一定能直接缩小一半的查找范围
…

看过之后的几个模版，并结合配套的例题，相信你会有自己的想法。

三、模版 I - 基础二分查找
模版 I 是基础的二分查找，用于查找可以通过访问数组中的单个索引来确定的元素或条件。
3.1 复杂度分析

平均时间复杂度： O(logN)
最坏时间复杂度： O(logN)
最优时间复杂度： O(1)

3.2 关键点

二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

3.3 区分语法

初始条件：


left = 0
right = arrar.length-1 或 number


终止：left > right
向左查找：right = mid-1
向右查找：left = mid+1

3.4 javascript 基础模版
var search = function(nums, target) {
  left = 0; // 初始左边界
  right = nums.length - 1; // 初始右边界
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2); //防止溢出
    if (nums[mid] < target) {
      // 收缩左边界
      left = mid + 1;
    } else if (nums[mid] > target) {
      // 收缩右边界
      right = mid - 1;
    } else {
      return mid; // 找到了当前值
    }
  }
  return -1;
};

3.5 代码分析

确定初始的左右边界:

left: 0
right: nums.length-1
mid: (left + (right - left) >> 1)


如果中间元素值nums[mid] < target：证明中间值左侧包括中间值都不符合要求，可以直接排除，left = mid + 1
如果中间元素值nums[mid]：证明中间值右侧包括中间值都不符合要求，可以直接排除，right = mid - 1
如果中间元素值nums[mid] = target：直接返回mid的下标
重新定义了左右边界，也需要重新计算中间值，我们需要继续进行范围的排除
定义搜索的条件，应该是搜索区间都不为空，即left <= right

3.6 LeetCode 实战
下面五题，难度递增，每篇题解都包含原题链接、模版分析、Js 题解，大家可以放心食用，我们一起加油～

二分查找（easy）
搜索插入的位置（easy）
x 的平方根（easy）
猜数字大小（easy）
搜索旋转排序数组（middle）


四、模版 II - 依赖当前元素与右元素的关系
模板 II 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
4.1 关键点

查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

4.2 区分语法

初始条件：left = 0, right = length 因为数组从下标0开始，所以实际代码中可以是 num.length - 1
终止：left <= right
向左查找：right = mid 这是因为向右判断，一般需要保留比较元素，否则某些晴情况下会丢失数据
向右查找：left = mid+1

4.3 javascript 基础模版
var search = function(nums, target) {
  left = 0; // 初始左边界
  right = nums.length - 1; // 初始右边界
  while (left <= right) {
    var mid = left + Math.floor(left + (right - left) / 2); //防止溢出
    if (target == nums[mid]) {
      right = mid + 1; // 继续寻找左侧是否仍存在满足条件的元素，但包含当前元素
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  if (left != nums.length && nums[left] === target) return left;
  return -1;
};

4.4 代码分析
首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。

终止搜索条件为 left <= right。
循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
如果 nums[mid] 等于目标值， 则收缩左边界，注意它此时不代表最终结果
如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候搜索区间可缩小为 [mid + 1, right]
如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候搜索区间可缩小为 [left, mid - 1]
最后我们要判断 left 值是否等于 target，如果不等于，证明没找到
如果 left 出了右边边界了，说明也没有找到

4.5 LeetCode 实战
下面 3 题，难度递增，每篇题解都包含原题链接、模版分析、Js 题解，大家可以放心食用，我们一起加油～

第一个错误的版本（easy）
寻找峰值（middle）
寻找旋转排序数组中的最小值（middle）


五、模板 III - 依赖当前元素与左右两个元素之间的关系
模板 III 是二分查找的另一种独特形式。它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
5.1 关键点

实现二分查找的另一种方法。
搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。当剩下 2个元素时，循环 / 递归结束。需要评估其余元素是否符合条件。

5.2 区分语法

初始条件：left = 0, right = length - 1
终止：left + 1 === right
向左查找：right = mid
向右查找：left = mid

5.3 javascript 基础模版
function binarySearch(nums, target) {
  const len = nums.length;
  if (len === 0) return -1;
  let left = 0;
  let right = len - 1;
  while (left + 1 < right) {
    let mid = left + ((right - left) >> 1);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid;
    } else {
      right = mid;
    }
  }
  if (nums[left] == target) return left;
  if (nums[right] == target) return right;
  return -1;
}

5.4 代码分析
因为我们的判断区间最少为 2 个元素，所以我们要注意循环的执行条件

简单的判断边界： nums.length === 0，return -1；
定义初始的左右边界：left = 0, right = nums.length - 1；
确定执行条件：left + 1 < right，这也意味着查找区间要存在 3 个元素；
向左查找时：right = mid；
向左查找时：left = mid；
判断剩下的两个元素哪个符合目标元素，并返回结果；

5.5 LeetCode 实战
下面 3 题，难度递增，每篇题解都包含原题链接、模版分析、Js 题解，大家可以放心食用，我们一起加油～

在排序数组中查找元素的第一个和最后一个位置（hard）


六、二分查找模板分析
本小结引自于LeetCode二分专题
上面提到的三个模版，大家在做题的时候很难完全套用进去，大部分时候，都是寻找最合适的方式并不断调整
6.1 模版差异
这 3 个模板的不同之处在于：


左、中、右索引的分配。
循环或递归终止条件。
后处理的必要性。

个人感觉模版I最实用（其实是另外两个模版掉头发啊！）
6.2 模版示例
模板I (left <= right)
二分查找的最基础和最基本的形式。

查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

模板II (left < right)
一种实现二分查找的高级方法。

查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

模板III (left + 1 < right)
实现二分查找的另一种方法。

搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。

七、其他经典问题

pow(n, x)
有效的完全平方数
寻找比目标字母大的最小字母
统计有序矩阵中的负数
矩阵中战斗力最弱的 K 行


八、写在最后
本文解释了三种最常见的解题模版，并附上LeetCode实战，帮助我们理解二分法这种思想。
如果对你有所帮助不妨给本项目的github 点个 star，这是对我最大的鼓励
关于我

花名：余光
WX：j565017805
沉迷 JS，水平有限，虚心学习中

其他沉淀

Github: Js 版 LeetCode 题解
前端进阶笔记
CSDN 博客汇总


	

问题描述：从json数组中，查找出满足指定定条件的数据。

解决方法：【filter()】



var employeesData = [
  { name: "王小明", mobile: "13900008789" },
  { name: "陈霞", mobile: "13900008789" },
  { name: "张悦", mobile: "13900008789" }
]

var queryData = employeesData.filter(function(fp) {
  return fp.name === "王小明"
})
console.log(queryData)

 

一、背景

分页应该是极为常见的数据展现方式了，一般在数据集较大而无法在单个页面中呈现时会采用分页的方法。

各种前端UI组件在实现上也都会支持分页的功能，而数据交互呈现所相应的后端系统、数据库都对数据查询的分页提供了良好的支持。

以几个流行的数据库为例：

查询表 t_data 第 2 页的数据(假定每页 5 条) 


	
MySQL 的做法：
	
select * from t_data limit 5,5

PostGreSQL 的做法：
select * from t_data limit 5 offset 5

MongoDB 的做法：
db.t_data.find().limit(5).skip(5);

尽管每种数据库的语法不尽相同，通过一些开发框架封装的接口，我们可以不需要熟悉这些差异。如 SpringData 提供的分页接口：

public interface PagingAndSortingRepository
  extends CrudRepository {

  Page findAll(Pageable pageable);
}

这样看来，开发一个分页的查询功能是非常简单的。

然而万事皆不可能尽全尽美，尽管上述的数据库、开发框架提供了基础的分页能力，在面对日益增长的海量数据时却难以应对，一个明显的问题就是查询性能低下！

那么，面对千万级、亿级甚至更多的数据集时，分页功能该怎么实现？

下面，我以 MongoDB 作为背景来探讨几种不同的做法。

二、传统方案

就是最常规的方案，假设 我们需要对文章 articles 这个表(集合) 进行分页展示，一般前端会需要传递两个参数：

- 页码(当前是第几页)

- 页大小(每页展示的数据个数)

按照这个做法的查询方式，如下图所示：

 



因为是希望最后创建的文章显示在前面，这里使用了_id 做降序排序。

其中红色部分语句的执行计划如下：

{
  "queryPlanner" : {
    "plannerVersion" : 1,
    "namespace" : "appdb.articles",
    "indexFilterSet" : false,
    "parsedQuery" : {
      "$and" : []
    },
    "winningPlan" : {
      "stage" : "SKIP",
      "skipAmount" : 19960,
      "inputStage" : {
        "stage" : "FETCH",
        "inputStage" : {
          "stage" : "IXSCAN",
          "keyPattern" : {
            "_id" : 1
          },
          "indexName" : "_id_",
          "isMultiKey" : false,
          "direction" : "backward",
          "indexBounds" : {
            "_id" : [ 
              "[MaxKey, MinKey]"
            ]
         ...
}

可以看到随着页码的增大，skip 跳过的条目也会随之变大，而这个操作是通过 cursor 的迭代器来实现的，对于cpu的消耗会比较明显。

而当需要查询的数据达到千万级及以上时，会发现响应时间非常的长，可能会让你几乎无法接受！

或许，假如你的机器性能很差，在数十万、百万数据量时已经会出现瓶颈

三、改良做法

既然传统的分页方案会产生 skip 大量数据的问题，那么能否避免呢？答案是可以的。

改良的做法为：

1. 选取一个唯一有序的关键字段，比如 _id，作为翻页的排序字段；

2. 每次翻页时以当前页的最后一条数据_id值作为起点，将此并入查询条件中。

如下图所示：



修改后的语句执行计划如下：

{
  "queryPlanner" : {
    "plannerVersion" : 1,
    "namespace" : "appdb.articles",
    "indexFilterSet" : false,
    "parsedQuery" : {
      "_id" : {
        "$lt" : ObjectId("5c38291bd4c0c68658ba98c7")
      }
    },
    "winningPlan" : {
      "stage" : "FETCH",
      "inputStage" : {
        "stage" : "IXSCAN",
        "keyPattern" : {
          "_id" : 1
        },
        "indexName" : "_id_",
        "isMultiKey" : false,
        "direction" : "backward",
        "indexBounds" : {
          "_id" : [ 
            "(ObjectId('5c38291bd4c0c68658ba98c7'), ObjectId('000000000000000000000000')]"
          ]
      ...
}

 可以看到，改良后的查询操作直接避免了昂贵的 skip 阶段，索引命中及扫描范围也是非常合理的！

性能对比

为了对比这两种方案的性能差异，下面准备了一组测试数据。

测试方案

准备10W条数据，以每页20条的参数从前往后翻页，对比总体翻页的时间消耗

db.articles.remove({});
var count = 100000;

var items = [];
for(var i=1; i<=count; i++){

  var item = {
    "title": "论年轻人思想建设的重要性-" + i,
    "author" : "王小兵-" + Math.round(Math.random() * 50),
    "type" : "杂文-" + Math.round(Math.random() * 10) ,
    "publishDate" : new Date(),
  } ;
  items.push(item);


  if(i%1000==0){
    db.test.insertMany(items);
    print("insert", i);

    items = [];
  }
}

传统翻页脚本

function turnPages(pageSize, pageTotal){

  print("pageSize:", pageSize, "pageTotal", pageTotal)

  var t1 = new Date();
  var dl = [];

  var currentPage = 0;
  //轮询翻页
  while(currentPage &lt; pageTotal){

     var list = db.articles.find({}, {_id:1}).sort({_id: -1}).skip(currentPage*pageSize).limit(pageSize);
     dl = list.toArray();

     //没有更多记录
     if(dl.length == 0){
         break;
     }
     currentPage ++;
     //printjson(dl)
  }

  var t2 = new Date();

  var spendSeconds = Number((t2-t1)/1000).toFixed(2)
  print("turn pages: ", currentPage, "spend ", spendSeconds, ".")  

}

改良翻页脚本

function turnPageById(pageSize, pageTotal){

  print("pageSize:", pageSize, "pageTotal", pageTotal)

  var t1 = new Date();

  var dl = [];
  var currentId = 0;
  var currentPage = 0;

  while(currentPage ++ &lt; pageTotal){

      //以上一页的ID值作为起始值
     var condition = currentId? {_id: {$lt: currentId}}: {};
     var list = db.articles.find(condition, {_id:1}).sort({_id: -1}).limit(pageSize);
     dl = list.toArray();

     //没有更多记录
     if(dl.length == 0){
         break;
     }

     //记录最后一条数据的ID
     currentId = dl[dl.length-1]._id;
  }

  var t2 = new Date();

  var spendSeconds = Number((t2-t1)/1000).toFixed(2)
  print("turn pages: ", currentPage, "spend ", spendSeconds, ".")    
}

以100、500、1000、3000页数的样本进行实测，结果如下：



可见，当页数越大(数据量越大)时，改良的翻页效果提升越明显！

这种分页方案其实采用的就是时间轴(TImeLine)的模式，实际应用场景也非常的广，比如Twitter、微博、朋友圈动态都可采用这样的方式。

而同时除了上述的数据库之外，HBase、ElasticSearch 在Range Query的实现上也支持这种模式。

四、完美的分页

时间轴(TimeLine)的模式通常是做成“加载更多”、上下翻页这样的形式，但无法自由的选择某个页码。

那么为了实现页码分页，同时也避免传统方案带来的 skip 性能问题，我们可以采取一种折中的方案。

这里参考Google搜索结果页作为说明：



通常在数据量非常大的情况下，页码也会有很多，于是可以采用页码分组的方式。
以一段页码作为一组，每一组内数据的翻页采用ID 偏移量 + 少量的 skip 操作实现

具体的操作如下图所示：



实现步骤


	
对页码进行分组(groupSize=8, pageSize=20)，每组为8个页码；
	
	

	
提前查询 end_offset，同时获得本组页码数量：
	
db.articles.find({ _id: { $lt: start_offset } }).sort({_id: -1}).skip(20*8).limit(1)

 分页数据查询以本页组 start_offset 作为起点，在有限的页码上翻页(skip)，由于一个分组的数据量通常很小(8*20=160)，在分组内进行skip产生的代价会非常小，因此性能上可以得到保证。
小结

随着物联网，大数据业务的白热化，一般企业级系统的数据量也会呈现出快速的增长。而传统的数据库分页方案在海量数据场景下很难满足性能的要求。

在本文的探讨中，主要为海量数据的分页提供了几种常见的优化方案(以MongoDB作为实例)，并在性能上做了一些对比，旨在提供一些参考。

来源：华为云社区  作者：zale

寻找最优的 TopN 算法




1 概要

在大量的数据记录中，依据某可排序的记录属性（一般为数字类型），找出最大的前 N 个记录，称为

TopN 问题。这是一个常常遇到的问题，也是一个比较简单的算法问题，却很少能有人能写出最优化的

topn 算法。本文对常见的 TopN 算法，进行分析比较，最后给出最优的 TopN 算法：基于小根堆的筛选

法.

2 问题定义

为了方便。我们把问题具体化：要求使用 C 语言来实现函数，在一个大小为 m 的，无序的整数数组中选

取最大的 n 个整数。即，问题定义为一个函数的实现:

int * topn(int *pdata, int m,int *ptop, int n);

其中，pdata 指向保存大量整数的内存，整数的个数为 m，要求函数把前 n 个最大的整数保存到 ptop 指

向的内存中,显然满足 m≥n≥0 。 同时假定 n<=m/2， 因为当 n 如果超过半数，可以问题转换为排

除 n−m/2个最小的整数----这种转换减少了问题规模。并且，已经实现选择 n 个最值（最大或最小）

的算法的情况下，排除 n 个最值的算法可以仿照实现。这里不再费时间叙述。

我们虽然假设的数据类型为整数，其他任意的数据类型，只要其数据是可以排序的，都可以根据这里的

算法，写出对应的算法实现。同样，我们虽然假定输入数据的方式为数组，实际输入的方式可以是任意

其他方式（如文件，数据库等）。

3 算法介绍

3.1 算法 1 完整排序法

对 pdata 中的数据，进行内部排序，然后选取前 n 个整数放到 ptop 中。如果使用较高效率的内部排序

算法（如：快速排序，堆排序），复杂度为 m∗log2

m .

使用这种算法，结果数据是从大到小排序的。

3.2 算法 2 基于有序数组的筛选法

保持 ptop 中的结果数组有序，即满足 ptop[0]≥ptop[1]≥...≥ptop[n−1] ，遍历 pdata 中的数

据，如果发现当前整数大于 ptop[n-1]就把数据插入到合适位置，以保持 ptop 中的仍然有序。算法复

杂度为. m∗n

使用这种算法，结果数据是从大到小排序的。显然，只从理论上的复杂度考虑，就可以看出来：当 n 较小的时候，算法 2 有较高的效率。但当 n 较大

的时候，算法 1 会有较高的效率。

仔细分析算法 2, 保持 ptop 中数据有序的目的，就是每次能找到最小的值，在有序数组中插入一个新元

素，最坏需要 n 次操作才能保持数组有序。其实要快速找到最小的值，使用小根堆更合适，因为中堆中

每次插入一个元素，最坏只需要 log2

n 次操作，根据这个思路产生下面的算法 3。

3.3 算法 3 基于小根堆的筛选法。

使用大小为 n 的小根堆保存结果集，最小项为堆的根节点 ptop[0],遍历 pdata 中，如果当前数据大于

ptop[0],并把数据替换根节点，并对根节点 SiftDown 操作，保持结果集仍然为小根堆。算法复杂度，

只有 m∗log2

n .- 更多关于小根堆的介绍，请看后面。

显然有，

m∗log2 nm∗log2 m , m∗log2 nm∗n

所以，算法 3 的复杂度最低。

这种算法，生成的结果数据是没有排序的。因为结果已经保存最小根堆种，如果需要排序，只需要完成

常规堆排序流程的后半部分，排序需要的复杂度只有 n。

4 实际测试结果

测试环境：

OS: Debain Linux kernel 2.6.26

C Complier: gcc 4.3.4

MEM: 768m

CPU: Intel(R) Pentium(R) 4 CPU 2.40GHz


5 算法分析

1. 在任何情况下，算法 3 都是最优的。但算法 3 的实现较复杂。

2. 如果不想实现复杂的算法 3，如果 n 相对于 m 很小，可以选择算法 2

3. 如果不想实现复杂的算法 3, 如果 n 比较大，例如：接近了 m/2, 可以选择算法 1

4. 如果不要求结果排序，算法 3 更有优势。

5. 算法 1 和算法 2，结果自然就排号顺序了。是否要求排序与其时间花费无关。

根据理论复杂度和实际的测试结果，更有下面的结论。

当 m 值固定，n 的变化区间为[1,m/2],三种算法消耗时间随 n 变化的曲线，如下面的图示意。相应的，当 n 固定，m 的变化区间为[2*n, ∞ ),三种算法消耗算法随 m 变化的曲线，如下面的图示意。




6 算法实现

6.1 算法 1 实现

使用标准 c 语言库支持的 qsort，直接就可以实现。

//用于比较操作的函数

static int cmpint(const void *p1, const void *p2)

{

return *((int *)p2) - *((int *)p1);

}

//算法实现

int * topn1(int *pdata, int m,int *ptop, int n)

{

qsort(pdata, m, sizeof(int),cmpint);

memcpy(ptop, pdata, n*sizeof(int));

return ptop;

}

注意：如果自己实现 qsort 算法，会有一定效率的提高。但代码级的优化，这里不会对效率产生本质的

影响。6.2 算法 2 实现

比较简单，源代码如下

int *topn2(int *pdata,int m,int *ptop,int n)

{

int i;

for(i=0;i<m;i++)

{

//判断当前结果集的大小（数组的长度）

int t = (i+1<n) ? (i+1):n;

if(i>=n && pdata[i] <= ptop[n-1])

continue;

int j=t-1;

for(;j>=1 && pdata[i]>ptop[j-1];j--)

ptop[j] = ptop[j-1];

ptop[j] = pdata[i];

}

return ptop;

}

注意：如果使用监视哨等优化手段，可以减少循环的判断条件。但这种代码级别的优化，这里不会对效

率产生本质的影响。

6.3 算法 3 实现

6.3.1 小根堆概念定义

小根堆精确定义：数组 x[1..n](注意，这里假定数组的第一个元素的索引为 1，是为了下面描述方便),

如果满足：

∀i∋[2,n], x[i/2]≤x [i]

就说明，这个数组就是小根堆

为了下面描述方便，我们定义对数组 x[1..n]的子数组 x[u..v]，（ 1≤u≤v≤n ）,如果满足：

∀i∋[2l, u],x[i/2]≤x [i]

就说明：x 整个数组的[u..v]部分已经是小根堆了。

6.3.2 我们需要的堆操作

//如果[2..n]已经是堆了，-除了第一个元素，其他部分已经是小根堆。

//通过下面的函数把第一个元素，往后交换，把整个数组变成堆。

void siftdown_head(int *pheap,int n)

{

pheap --; //这样作是让第一个元素的索引变成 1, pheap[0]永远不会被访问到int t = pheap[1];

int i =1;

int c = i*2;

while(c<=n)

{

if(c<n && pheap[c]>pheap[c+1])

c++;

if(pheap[c] < t)

{

pheap[i] = pheap[c];

i = c;

c = 2*i;

}

else

break;

}

pheap[i] = t;

}

//如果除了最后一个元素外，其他部分[1..n-1]已经是堆了，

//通过下面的函数，把最后一个元素往前交换，把整个数组调整成堆

void siftup_rear(int *pheap,int n)

{ 

pheap --;

int t = pheap[n];

int i;

for(i=n; i>1;)

{

int p = i/2;

if( pheap[p] > t)

pheap[i] = pheap[p];

else

break;

i=p;

}

pheap[i] =t;

}

更多关于堆的概念，可以在网上找到。最常见的应用是使用堆来实现高效率的优先级队列（如 c++的标

准模板库）。在本文应用场景中，也可以把保存 topn 结果的数组看成是优先级队列，因为我们总是选择

数值最小的值，进行出队操作（数值越小，优选级越大）。最后，队列中剩余的，自然就是数值较大的

topn 结果。

6.3.3 算法实现

int * topn3(int *pdata, int m,int *ptop, int n){

ptop[0] = pdata[0];

int i;

for(i=1; i<n;i++)

{

ptop[i] = pdata[i];

siftup_rear(ptop,i+1);

}

for(i=n;i<m;i++)

{

register t = pdata[i];

if(ptop[0] >= t)

continue;

ptop[0] = t;

siftdown_head(ptop,n);

;

}

//如果不需要把结果排序，下面的这段循环可以乎略掉

for(i=n-1; i>=1;i--)

{

int t = ptop[i];

ptop[i] = ptop[0];

ptop[0] = t;

siftdown_head(ptop,i);

}

return ptop;

}

其实，在本文问题定义下，也可以直接使用 c++标准库的模板种的优先级队列，来实现 topn 算法。

 
转自mail:cuichaox @gmail.com 
转自blog: http://cuichaox.cublog.cn