heapSort

算法: 堆排序

• 堆分析
  堆排序适合于求”前K大问题” 海量输出中找出前几大数据

  堆排序->二叉树模型
      父节点
       (3)
      /   \
     /     \
   (2)     (1)
  左孩子    右孩子

  堆排序两种情况
  大根堆：父节点要比左右孩子都大
  小根堆：父节点要比左右孩子都小
  堆排序需要做两件事：
  第一：构建大根堆

          (3)
         /   \
        /     \
      (2)    (1)
     /   \
    /     \
  (4)     (5)

  上面的树是一个无序堆，构建大根堆步骤如下：
  第一步：首先找到堆中的2个父节点（2,3）;
  第二步：比较2这个父节点的两个孩子(4,5)，发现5大
  第三步：将较大的右孩子(5)跟父节点(2)进行交换，至此3的左孩子对构建完成，
  如下所示

         (3)
        /   \
       /     \
     (5)     (1)
    /   \
   /     \
  (4)    (2)

  第四步：比较第二个父节点(3)下面的左右孩子(5,1),发现左孩子5大
  第五步：然后父节点（3）与左孩子（5）进行交换，注意，交换后，堆可能会遭到破坏，
  按照以上步骤一，步骤二，步骤三进行重新构造堆。

  最后构造的堆如下

          (5)
         /   \
        /     \
      (4)     (1)
     /   \
    /     \
  (3)     (2)

  第二：输出大根堆
  至此，我们把大根堆构造出来了，那怎么输出呢？我们做大根堆的目的就是要找出最大值，
  那么我们将堆顶（5）与堆尾（2）进行交换，然后将（5）剔除根堆，由于堆顶现在是（2），
  所以破坏了根堆，必须重新构造，构造完之后又会出现最大值，再次交换和剔除，最后也就
  是要的效果

• 构建堆heapAdjust
  @param list 数组(待排序集合)
  @param parent 父节点
  @param lenght 输出根堆时剔除最大值使用

function heapAdjust(list, parent, length) {
    //temp 保存当前父节点
    var temp = list[parent];
    //得到左孩子（二叉树定义）
    var child = 2 * parent + 1;
    while (child < length) {
        //如果parent有右孩子，则判断左孩子是否小于右孩子
        if (child + 1 < length && list[child] < list[child + 1]) {
            child++;
        }
        //如果父节点大于子节点，就不用交换
        if (temp >= list[child]) {
            break;
        }
        //将较大子节点的值赋给父节点
        list[parent] = list[child];
        //然后将子节点作为父节点，防止是否破坏根堆时重新构造
        parent = child;
        //找到该父节点较小的左孩子节点
        child = 2 * parent + 1;
    }
    //最后将temp值赋给较大的子节点，以形成两值交换
    list[parent] = temp;
}

• 堆排序heapSort

@param list 待排序数组
@param top 前K大

function heapSort(list, top) {
    //需要输出的集合
    var topNode = [];
    //list.length/2-1 为堆中父节点个数
    for (var i = list.length / 2 - 1; i >= 0; i--) {
        heapAdjust(list, i, list.length);
    }
    //最后输出堆元素
    for (var i = list.length - 1; i >= list.length - top ; i--) {
        //堆顶与当前堆得第一个元素进行值对调
        var temp = list[0];
        list[0] = list[i];
        list[i] = temp;

        //最大值添加到输出集合
        topNode.push(temp);
        //因为顺序被打乱，重新构造堆
        heapAdjust(list, 0, i);
    }
    return topNode;
}

• 调用

//获取一个随机数组
function getDatalist() {
    var listarr = [];
    for (var j = 0; j < 20000; j++) {
        listarr[j] = Math.ceil(Math.random() * 20000);
    }
    return listarr;
}
// 调用
//var list = getDatalist();
//var toplist = heapSort(list, 10);
var list1 = [50, 20, 80, 60, 75, 33, 25, 85, 66, 55];
var toplist1 = heapSort(list1, 3);