ES6的JavaScript数据结构实现之二叉堆和堆排序

目的：ES6标准下的JS数据结构的一些实现代码。（作为记录和启发）

内容：二叉堆和堆排序。（未完成，待继续）

所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript数据结构实现之二叉堆和堆排序

一、基础数据结构

1、二叉堆（最小堆和最大堆；插入值（保持最小堆或最大堆结构）；找到最大值或者最小值；移除最小堆的最小值（堆的根节点））

基本概念：二叉堆是一种特殊的二叉树，其有两个特性：结构特性和堆特性。结构特性是指它是一颗完全的二叉树（树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点）。堆特性是指二叉堆不是最小堆就是最大堆（最小堆可以快速导出树的最小值，最大堆可以快速导出树的最大值），所有的节点都大于等于（最大堆）或者小于等于（最小堆）每个它的子节点。

1.1 最小堆

  1 const Compare = {
  2   LESS_THAN: -1,
  3   BIGGER_THAN: 1,
  4   EQUALS: 0
  5 };
  6 
  7 function defaultCompare(a, b) {
  8   if (a === b) {
  9     return Compare.EQUALS;
 10   }
 11   return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
 12 }
 13 
 14 function swap(array, a, b) {
 15   /* const temp = array[a];
 16   array[a] = array[b];
 17   array[b] = temp; */
 18   [array[a], array[b]] = [array[b], array[a]];
 19 }
 20 function reverseCompare(compareFn) {
 21   return (a, b) => compareFn(b, a);
 22 }
 23 class MinHeap {
 24   constructor(compareFn = defaultCompare) {
 25     this.compareFn = compareFn;
 26     this.heap = [];
 27   }
 28   getLeftIndex(index) {
 29     return 2 * index + 1;
 30   }
 31   getRightIndex(index) {
 32     return 2 * index + 2;
 33   }
 34   getParentIndex(index) {
 35     if (index === 0) {
 36       return undefined;
 37     }
 38     return Math.floor((index - 1) / 2);
 39   }
 40 
 41   size() {
 42     return this.heap.length;
 43   }
 44 
 45   isEmpty() {
 46     return this.size() <= 0;
 47   }
 48 
 49   clear() {
 50     this.heap = [];
 51   }
 52   findMinimum() {
 53     return this.isEmpty() ? undefined : this.heap[0];
 54   }
 55   insert(value) {
 56     if(value != null) {
 57       this.heap.push(value);
 58       const index = this.heap.length - 1;
 59       this.siftUp(index);
 60       return true; 
 61     }
 62     return false;
 63   }
 64   siftUp(index) {
 65     let parent = this.getParentIndex(index);
 66     while (
 67       index > 0 
 68       && this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN 
 69       ) {
 70       swap (this.heap, parent, index );
 71       index = parent;
 72       parent = this.getParentIndex(index);
 73     }
 74   }
 75   extract() {
 76     if (this.isEmpty()) {
 77       return undefined;
 78     }
 79     if (this.size() == 1) {
 80       return this.heap.shift();
 81     }
 82     const removedValue = this.heap[0];
 83     this.heap[0] = this.heap.pop();
 84     this.siftDown(0);
 85     return removedValue;
 86   }
 87   siftDown(index) {
 88     let element = index;
 89     const left = this.getLeftIndex(index);
 90     const right = this.getRightIndex(index);
 91     const size = this.size();
 92     if (
 93       left < size 
 94       && this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN
 95       ) {
 96       element = left;
 97     } else if (
 98       right < size
 99       && this.compareFn(this.heap[element], this.heap[right] === Compare.BIGGER_THAN)
100       ) {
101       element = right;
102     }
103     if(index !== element) {
104       swap(this.heap, index, element);
105       this.siftDown(element); 
106     }
107   }
108   heapify(array) {
109     if (array) {
110       this.heap = array;
111     }
112     const maxIndex = Math.floor(this.size() / 2) - 1;
113     for (let i = 0; i <= maxIndex; i++) {
114       this.siftDown(i);
115     }
116     return this.heap;
117   }
118 
119   getAsArray() {
120     return this.heap;
121   }
122 
123 
124 }
125 
126 const heap = new MinHeap();
127 heap.insert(2);
128 heap.insert(3);
129 heap.insert(4);
130 heap.insert(5);
131 console.log(heap);
132 heap.insert(1);
133 console.log(heap);
134 console.log(heap.findMinimum());
135 heap.clear();
136 const heap1 = new MinHeap();
137 for (let i = 1; i < 10; i++) {
138   heap.insert(i);
139 }
140 console.log(heap);
141 console.log(heap.extract());
142 console.log(heap);

MinHeap

1.2 最大堆

把最小堆中的比较函数修改为相反的就行了，即把最小堆中的所有大于的比较换成小于的比较。

1 class MaxHeap extends MinHeap {
2   constructor(compareFn = defaultCompare) {
3     super(compareFn);
4     this.compareFn = compareFn;
5     this.compareFn = reverseCompare(compareFn);
6   }

MaxHeap

二、简单应用

1、堆排序

思路：用数组创建一个最大堆；最大的值放置堆的最后一个位置；将堆的大小减一，每次执行第二个步骤直至堆的大小为1。（这样就得到升序（从最小到最大）的数组，若要数组的降序排列，则我们用最小堆。）

 1 function heapify(array, index, heapSize, compareFn) {
 2   let largest = index;
 3   const left = (2 * index) + 1;
 4   const right = (2 * index) + 2;
 5   if (left < heapSize && compareFn(array[left], array[index]) > 0) {
 6     largest = left;
 7   }
 8   if (right < heapSize && compareFn(array[right], array[largest]) > 0) {
 9     largest = right;
10   }
11   if (largest !== index) {
12     swap(array, index, largest);
13     heapify(array, largest, heapSize, compareFn);
14   }
15 }
16 
17 function buildMaxHeap(array, compareFn) {
18   for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
19     heapify(array, i, array.length, compareFn);
20   }
21   return array;
22 }
23 
24 function heapSort(array = [], compareFn = defaultCompare) {
25   let heapSize = array.length;
26   buildMaxHeap(array, compareFn);
27   while (heapSize > 1) {
28     swap(array, 0, --heapSize);
29     heapify(array, 0, heapSize, compareFn);
30   }
31   return array;
32 }
33 
34 const heapSort1 = new heapSort();
35 const array = [7, 6, 3, 5, 4, 1, 2];
36 
37 console.log('Before sorting: ', array);
38 console.log('After sorting: ', heapSort(array));

HeapSort