Heap

堆是通过一维数组来实现的树结构。

堆节点的访问

在数组起始位置为 0 的情形中:

• 父节点 i 的左子节点在位置 (2i + 1);
• 父节点 i 的右子节点在位置 (2i + 2);
• 子节点 i 的父节点在位置 Math.floor((i - 1) / 2);

Max Heap && Min Heap

• Max Heap: 每个节点都大于等于左右子节点的值。用于升序排序。见 heap_sort

8
        ↙     ↘
     3          7
  ↙    ↘      ↙   ↘
2        1  5        4

• Min Heap: 每个节点都小于等于左右子节点的值。用于降序排序。

1
        ↙    ↘
      2        4
   ↙    ↘    ↙   ↘
  5       3 8      7

Priority Queue Based Heap

It's usually to use the two ways called enqueue and dequeue:

• enqueue(value): insert value into the heap;
  • Because the value is inserted into the last heap, we'll use sift up to adjust position;

10
        ↙     ↘
     3          7
           |
           ↓
      `enqueue(9)`
           10
        ↙     ↘
     3          7
  ↙ sift up
9
           |
           ↓
           10
        ↙     ↘
     9          7
  ↙ sift up
3

• dequeue(): to pick the smallest or the biggest element from the heap;
  • It'll swap the endest element with the first element, and then keep the heap length reduce 1. If so, only do once sift down operation in the first element to heapify.

8
        ↙     ↘
     3          7
  ↙    ↘      ↙   ↘
2        1  5       4
          |
  pick 8, move 4 to top
          ↓

           4
        ↙     ↘ (swap)
     3          7
  ↙    ↘      ↙
2        1  5
          |
  sift down 4 to rebuild max heap.
          ↓

           7
        ↙     ↘
     3          4
  ↙    ↘      ↙
2        1  5
          |
  redo the last steps
          ↓
           7
        ↙     ↘
     3          5
  ↙    ↘      ↙
2        1  4

var len

/**
 * to build max heapify from bottom to top;
 * the last subscript's parent subscript is Math.floor((len - 1) / 2)
 */
var buildMaxHeapify = function(arr) {
  len = arr.length

  for (let i = Math.floor((len - 1) / 2); i >= 0; i--) {
    siftDown(arr, i)
  }
  return arr
}

/**
 * Insert a value into heap. It's an operation called sift up.
 */
var enqueue = function(arr, value) {
  arr.splice(len, 0, value)
  len++
  siftUp()
}

/**
 * to keep max heap, it's an operation called sift up.
 */
var siftUp = function() {
  let enqueueValSubscript = len - 1
  let parent = Math.floor(enqueueValSubscript / 2)
  while (parent > 0 && arr[parent] < arr[enqueueValSubscript]) {
    swap(arr, parent, enqueueValSubscript)
    enqueueValSubscript = parent
    parent = Math.floor(enqueueValSubscript / 2)
  }
}

/*
 * to pick the smallest or the biggest element from the heap and return it;
 * Then t'll swap the endest element with the first element, and then keep the
 * heap length reduce one. If so, only do once sift down operation in the first element to keep heapify.
 */
var dequeue = function() {
  const maxValue = arr[0]
  swap(arr, len - 1, 0)
  len--
  siftDown(arr, 0)
  return maxValue
}

/**
 * to keep max heap, it's an operation called sift down.
 */
var siftDown = function(arr, i) {
  const left = 2 * i + 1
  const right = 2 * i + 2
  let maxSubscript = i

  if (left < len && arr[left] > arr[maxSubscript]) {
    maxSubscript = left
  }

  if (right < len && arr[right] > arr[maxSubscript]) {
    maxSubscript = right
  }

  if (maxSubscript !== i) {
    swap(arr, maxSubscript, i)
    siftDown(arr, maxSubscript)
  }
}

// swap two value in arr
var swap = function(arr, pointOne, pointTwo) {
  const tmp = arr[pointOne]
  arr[pointOne] = arr[pointTwo]
  arr[pointTwo] = tmp
}

Test case one:

input: var arr = [5, 2, 7, 3, 1, 8, 4]

buildMaxHeapify(arr) // [8, 3, 7, 2, 1, 5, 4]
           8                                           8
        ↙     ↘          enqueue(arr, 6)            ↙     ↘
     3          7        --------------->         6          7
  ↙    ↘      ↙   ↘                            ↙    ↘      ↙   ↘
2        1  5       4                        3        1   5       4
                                           ↙
                                         2

                                     7
        return 8                  ↙     ↘
        dequeue()               6         5
    ---------------->        ↙    ↘     ↙   ↘
                           3       1   2      4