Priority Queues, Heap Sort

[barretlee]

排序这块我们已经讨论很多了（ #6 #8 #9 #10 )，从最开始基本的冒泡、插入、选择和希尔排序，到分治思想的延伸——归并排序（自顶向下和自底向上），再到归并排序的互补算法——快排，然后学习了新的数据结构——二叉堆，于是有了堆排序。

二叉堆是一种数据结构，他的每一个二叉树点元素数值都会比下面两个节点元素的数值要大，因为这种数据接口包含的信息量很大，而得到这种数据结构的成本是很低的，构建一个二叉堆的算法并不复杂：

/chapters/chapter-2-sorting/2.4-priority-queues/priorityQueueAdd.js

function priorityQueueAdd(input) {
  var output = [];

  output[1] = input[0];
  for(var i = 1, len = input.length; i < len; i++) {
    output = swim(output, input[i]);
  }

  return output;

  function swim(arr, val) {
    arr.push(val);
    var k = arr.length - 1;
    while(k > 1 && arr[k >> 1] < arr[k]) {
      var p = k >> 1;
      arr[p] = [arr[k], arr[k] = arr[p]][0];
      k = p;
    }
    return arr;
  }
}

通过上浮的方式，不断插入新元素，既可形成一个二叉堆。这种优先队列最大的特点是，能够拿到很快拿到最大元素（顶部），当这个最大元素被删除（优先级最高的事务被处理完成）时，还能快速高效地将剩下的元素重整为一个二叉堆：

/chapters/chapter-2-sorting/2.4-priority-queues/priorityQueueDelete.js

function priorityQueueDelete(input) {
  var output = [];

  input.splice(1, 1);
  output = sink(input);

  return output;

  function sink(arr) {
    arr.splice(1, 0, arr.pop());
    var k = 1, N = arr.length - 1;
    while(2 * k <= N) {
      var j = 2 * k;
      if(j < N && arr[j] < arr[j + 1]) j++;
      if(arr[k] >= arr[j]) break;
      arr[k] = [arr[j], arr[j] = arr[k]][0];
      k = j;
    }
    return arr;
  }
}

一个二叉堆能够快速拿到最大元素，并且能够立即重新调整为二叉堆，基于这个特性，就有了堆排序：

/chapters/chapter-2-sorting/2.4-priority-queues/heapSort.js

function heapSort(input) {
  return sort(input);

  function sort (arr){
    var N = arr.length - 1;
    for(var k = N >> 2; k >= 1; k--) {
      arr = sink(arr, k, N);
    }
    while(N > 1) {
      arr[1] = [arr[N], arr[N] = arr[1]][0];
      N--;
      arr = sink(arr, 1, N);
    }
    return arr;
  }
  function sink(arr, k, N) {
    while(2 * k <= N) {
      var j = 2 * k;
      if(j < N && arr[j] < arr[j + 1]) j++;
      if(arr[k] >= arr[j]) break;
      arr[k] = [arr[j], arr[j] = arr[k]][0];
      k = j;
    }
    return arr;
  }
}

光看代码还是挺难理解的，脑海中必须有一个数组储存的堆模型。for 循环构造了堆（从 N/2 开始，跳过了所有大小为 1 的堆），注意，这里构造的并不是二叉堆，然后 while 循环将最大的元素 a[1] 和 a[n] 交换位置并修复堆，如此循环直到堆为空。

上面的排序用到的是 sink 方法，而 swim 方法也是可以用于排序算法之中的，这就是对应的下沉排序，感觉有点难理解。