JS数据结构之堆

• JS 中通常用数组表示堆
• 左侧子节点的位置是 2*index + 1
• 右侧子节点的位置是 2*index + 2
• 父节点位置是 (index-1)/2
• 堆能高效、快速地找出最大值和最小值，时间复杂度：O(1)
• 找出第K个最大（最小）元素

let heap = [];
function swap(index1, index2) {
  let temp;
  temp = heap[index1];
  heap[index1] = heap[index2];
  heap[index2] = temp;
}
function shiftup(index) {
  let parentIndex = (index - 1) >> 1// Math.floor((index - 1) / 2);
  if (index != 0 && heap[parentIndex] < heap[index]) { swap(parentIndex, index); shiftup(parentIndex); } } function shiftDown(index) { let leftNodeIndex = (index + 1) * 2 - 1, rightNodeIndex = (index + 1) * 2 if (leftNodeIndex < heap.length && heap[leftNodeIndex] > heap[index]) {
    swap(leftNodeIndex, index);
    shiftDown(leftNodeIndex);
  } else if (rightNodeIndex < heap.length && heap[rightNodeIndex] > heap[index]) {
    swap(rightNodeIndex, index);
    shiftDown(rightNodeIndex);
  }
}
function insert(val) {
  heap.push(val);
  shiftup(heap.length - 1);
}
function remove() {
  swap(0, heap.length - 1);
  heap.pop();
  shiftDown(0);
  return heap[0];
}
insert(1);
insert(3);
insert(2);
insert(5);
remove();
insert(4);
insert(6);
remove();
console.log(heap);//[ 4, 3, 2, 1 ]

/* 排序思路：（降序）
 * 将堆根保存于尾部，并对剩余序列调用调整函数，调整完成后，再将最大跟保存于尾部-1（-1，-2，...，-i），
 * 再对剩余序列进行调整，反复进行该过程，直至排序完成。
 */

/* 将最大的元素调整到堆顶*/
function AdjustHeap(arr, pos, len){
    var swap = arr[pos];      //保存当前节点
    var child = pos * 2 + 1;  //定位到当前节点的左边的子节点
    while(child < len){       //递归遍历所有的子节点
        //判断当前节点是否有右节点，若右节点较大，就采用右节点和当前节点进行比较
        if(child + 1 < len && arr[child] < arr[child + 1]){
            child += 1;
        }
        //比较当前节点和最大的子节点，小于就交换，交换后将当前节点定位到子节点上
        if(arr[pos] < arr[child]){
            arr[pos] = arr[child];
            pos = child;
            child = pos * 2 + 1;
        }
        else{
            break;
        }
        arr[pos] = swap;
    }
}

/* 构建堆：
 * 满足：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子结点的关键字。
 * 实现：从最后一个拥有子节点的节点开始，将该节点和其他节点进行比较，将最大的数交换给该节点，
 *      交换后再依次向前节点进行相同的交换处理，直到构建出大顶堆。
 */
function BuildHeap(arr){
  for(var i=arr.length/2; i>=0; i--){  //构建打顶堆
      AdjustHeap(arr, i, arr.length);
  }
}

/*堆排序算法*/
function HeapSort(arr){
    BuildHeap(arr); //构建堆
    for(var i=arr.length-1; i>0; i--){   //从数组的尾部进行调整
        var swap = arr[i];  //堆顶永远是最大的元素,将堆顶和尾部元素交换，最大元素就保存在尾部，并且不参与后面的调整
        arr[i] = arr[0];
        arr[0] = swap;
        AdjustHeap(arr, 0, i); //将最大的元素进行调整，将最大的元素调整到堆顶
    }
}

var arr = [46,12,33,72,68,19,80,33];
console.log('before: ' + arr);
HeapSort(arr);
console.log(' after: ' + arr);