十六、堆

本章将介绍堆。堆是一种重要的数据结构，它在 O(1)时间内返回最高或最低的元素。本章将重点解释堆是如何实现的，以及如何使用它们。一个例子是堆排序，这是一种基于堆的排序算法。

了解堆

堆是一种类似树的数据结构，其中父堆大于其子堆(如果是最大堆)或小于其子堆(如果是最小堆)。堆的这一属性使它对数据排序非常有用。

与其他树数据结构不同，堆使用数组来存储数据，而不是拥有指向其子级的指针。堆节点的子节点在数组中的位置(索引)很容易计算。这是因为父子关系很容易用堆来定义。

有许多类型的堆有不同数量的子堆。在本章中，只考虑二进制堆。因为堆使用数组来存储数据，所以数组的索引定义了每个元素的顺序/高度。二进制堆可以通过将第一个数组元素作为根元素，然后依次填充每个左边和右边的元素来构建。

例如，对于图 16-1 中所示的堆，数组应该是这样的:[2，4，23，12，13]。

img/465726_1_En_16_Fig1_HTML.jpg

图 16-1

堆索引

有两种类型的二进制堆:最大堆和最小堆。在 max-heap 中，根节点的值最高，每个节点的值都大于其子节点。在最小堆中，根节点的值最低，每个节点的值都小于其子节点。

堆可以存储任何类型的任何值:字符串、整数，甚至自定义类。如第 3 和 4 章所述，字符串和整数值的比较由 JavaScript 本地处理(例如，9 大于 1， z 大于 a )。然而，对于定制类，开发人员需要实现一种方法来比较两个类。本章将着眼于只存储整数值的堆。

最大堆

最大堆是指父堆总是大于其子堆的堆(见图 16-2 )。

img/465726_1_En_16_Fig2_HTML.jpg

图 16-2

最大堆

这里是 max-heap 的数组，如图 16-2 所示:[100，19，36，17，3，25，1，2，7]。

最小堆

最小堆是一个父堆总是比它的任何子堆都小的堆(见图 16-3 )。

img/465726_1_En_16_Fig3_HTML.jpg

图 16-3

最小堆

这里是如图 16-3 所示的 max-heap 的数组:[1，2，3，17，19，36，7，25，100]。

二进制堆数组索引结构

对于二进制堆，通过使用以下索引，使用数组来表示堆，其中N是节点的索引:

Node                Index
(itself)            N
Parent              (N-1) / 2
Left Child          (N*2) + 1
Right Child         (N*2) + 2

图 16-4 用指数说明了这种家族关系。

img/465726_1_En_16_Fig4_HTML.jpg

图 16-4

堆关系

让我们首先定义一个通用的Heap类。使用前面描述的索引结构，一个数组将被用来存储所有的值。下面的堆类实现了检索父节点、左侧子节点和右侧子节点的帮助器函数。下面的代码块有一个peek函数，它返回最大堆的最大值和最小堆的最小值。

 1   function Heap() {
 2       this.items = [];
 3   }
 4
 5   Heap.prototype.swap = function(index1, index2) {
 6       var temp = this.items[index1];
 7       this.items[index1] = this.items[index2];
 8       this.items[index2] = temp;
 9   }
10
11   Heap.prototype.parentIndex = function(index) {
12       return Math.floor((index - 1) / 2);
13   }
14
15   Heap.prototype.leftChildIndex = function(index) {
16       return index * 2 + 1;
17   }
18
19   Heap.prototype.rightChildrenIndex = function(index) {
20       return index * 2 + 2;
21   }
22
23   Heap.prototype.parent = function(index) {
24       return this.items[this.parentIndex(index)];
25   }
26
27   Heap.prototype.leftChild = function(index) {
28       return this.items[this.leftChildIndex(index)];
29   }
30
31   Heap.prototype.rightChild = function(index) {
32       return this.items[this.rightChildrenIndex(index)];
33   }
34
35   Heap.prototype.peek = function(item) {
36       return this.items[0];
37   }
38   Heap.prototype.size = function() {
39       return this.items.length;
40   }

size函数是另一个返回堆大小(元素数量)的助手。

渗透:上下冒泡

当添加或删除元素时，堆的结构必须保持不变(最大堆的节点大于其子节点，最小堆的节点小于其子节点)。

这需要交换项目并“冒泡”到堆的顶部。与向上冒泡类似，有些项需要“向下冒泡”到它们正确的位置，以便保持堆的结构。逾渗在时间上需要 O(log2(n))。

让我们遍历一个 min-heap 示例，并按以下顺序将以下值插入 min-heap:12、2、23、4、13。以下是步骤:

img/465726_1_En_16_Fig11_HTML.jpg

图 16-11

最新和最大的 13 节点仍在原处

  1. 插入 13，如图 16-11 所示。

img/465726_1_En_16_Fig10_HTML.jpg

图 16-10

较小的 4 节点已经冒泡以维持最小堆结构

  1. 12 与 4 交换以保持最小堆结构(图 16-10 )。

img/465726_1_En_16_Fig9_HTML.jpg

图 16-9

最小堆中的新节点比它上面的节点小

  1. 在堆中插入 4，如图 16-9 所示。

img/465726_1_En_16_Fig8_HTML.jpg

图 16-8

较大的 23 节点保留在最小堆结构中

  1. 在第二个子位置插入一个新的 23 节点(图 16-8 )。

img/465726_1_En_16_Fig7_HTML.jpg

图 16-7

较小的节点直到父节点位置都有气泡

  1. 2 节点会冒泡，因为它小于 12，因此应该位于最小堆的顶部(图 16-7 )。

img/465726_1_En_16_Fig6_HTML.jpg

图 16-6

最新的节点比父节点小

  1. 插入一个新的 2 节点(图 16-6 )。

img/465726_1_En_16_Fig5_HTML.jpg

图 16-5

最小堆根节点

  1. 插入 12 作为第一个节点(图 16-5 )。

下面是这个堆的数组内容:[2，4，23，12，13]。

实现渗透

为了实现渗滤的“上下冒泡”,交换直到最小堆结构形成，最小元素在顶部。对于向下冒泡，如果一个子元素更小，则将顶部元素(数组中的第一个)与其子元素交换。同样，对于向上冒泡，如果父元素大于新元素，则将新元素与其父元素交换。

 1   function MinHeap() {
 2       this.items = [];
 3   }
 4   MinHeap.prototype = Object.create(Heap.prototype); // inherit helpers from heap by copying prototype
 5   MinHeap.prototype.bubbleDown = function() {
 6       var index = 0;
 7       while (this.leftChild(index) && this.leftChild(index) < this.items[index]) {
 8           var smallerIndex = this.leftChildIndex(index);
 9           if (this.rightChild(index)
10               && this.rightChild(index) < this.items[smallerIndex]) {
11              // if right is smaller, right swaps
12               smallerIndex = this.rightChildrenIndex(index);
13           }
14           this.swap(smallerIndex, index);
15           index = smallerIndex;
16       }
17   }
18
19   MinHeap.prototype.bubbleUp = function() {
20       var index = this.items.length - 1;
21       while (this.parent(index) && this.parent(index) > this.items[index]) {
22           this.swap(this.parentIndex(index), index);
23           index = this.parentIndex(index);
24       }
25   }

最大堆实现的不同之处仅在于比较器。对于向下冒泡，如果子节点更大，则 max-heap 节点与其一个子节点交换。同样，对于冒泡，如果最新节点的父节点比新节点小，则该节点与其父节点交换。

最大堆示例

现在让我们构建一个 max-heap，其值与前面的 min-heap 示例中使用的值相同，按顺序插入以下值:12、2、23、4、13。

img/465726_1_En_16_Fig19_HTML.jpg

图 16-19

渗透恢复最大堆结构

  1. 由于 max-heap 结构，13 和 4 交换位置(图 16-19 )。

img/465726_1_En_16_Fig18_HTML.jpg

图 16-18

新节点比它上面的节点大

  1. 插入 13，如图 16-18 所示。

img/465726_1_En_16_Fig17_HTML.jpg

图 16-17

4 和 2 节点交换位置

  1. 为了保持最大堆结构，4 个气泡向上，2 个气泡向下(图 16-17 )。

img/465726_1_En_16_Fig16_HTML.jpg

图 16-16

新节点比它上面的节点大

  1. 插入 4，如图 16-16 所示。

img/465726_1_En_16_Fig15_HTML.jpg

图 16-15

新的较大节点与较小的 12 交换

  1. 这 23 个节点“冒泡”到顶部以维持最大堆结构(图 16-15 )。

img/465726_1_En_16_Fig14_HTML.jpg

图 16-14

新子节点大于父节点

  1. 插入 23，如图 16-14 所示。

img/465726_1_En_16_Fig13_HTML.jpg

图 16-13

新的较小节点保留在最大堆结构中

  1. 插入一个新的 2 节点(图 16-13 )。

img/465726_1_En_16_Fig12_HTML.jpg

图 16-12

第一个最大堆节点

  1. 插入第一个节点，即 12(图 16-12 )。

下面是这个堆的数组内容:[23，13，12，2，4]。

最小堆完成实现

将所有定义的函数放在一起并继承Heap的函数，min-heap 的完整实现和示例如下所示。增加了add和poll功能。add简单地向堆中添加一个新元素，但是bubbleUp确保最小堆中的这个元素满足顺序。poll从堆中移除最小元素(根),并调用bubbleDown来保持最小堆顺序。

 1   function MinHeap() {
 2       this.items = [];
 3   }
 4   MinHeap.prototype = Object.create(Heap.prototype); // inherit helpers from heap by copying prototype
 5   MinHeap.prototype.add = function(item) {
 6       this.items[this.items.length] = item;
 7       this.bubbleUp();
 8   }
 9
10   MinHeap.prototype.poll = function() {
11       var item = this.items[0];
12       this.items[0] = this.items[this.items.length - 1];
13       this.items.pop();
14       this.bubbleDown();
15       return item;
16   }
17
18   MinHeap.prototype.bubbleDown = function() {
19       var index = 0;
20       while (this.leftChild(index) && (this.leftChild(index) < this.items[index] || this.rightChild(index) < this.items[index]) ) {
21           var smallerIndex = this.leftChildIndex(index);
22           if (this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) {
23               smallerIndex = this.rightChildrenIndex(index);
24           }
25           this.swap(smallerIndex, index);
26           index = smallerIndex;
27       }
28   }
29
30   MinHeap.prototype.bubbleUp = function() {
31       var index = this.items.length - 1;
32       while (this.parent(index) && this.parent(index) > this.items[index]) {

33           this.swap(this.parentIndex(index), index);
34           index = this.parentIndex(index);
35       }
36   }
37
38   var mh1 = new MinHeap();
39   mh1.add(1);
40   mh1.add(10);
41   mh1.add(5);
42   mh1.add(100);
43   mh1.add(8);
44
45   console.log(mh1.poll()); // 1
46   console.log(mh1.poll()); // 5
47   console.log(mh1.poll()); // 8
48   console.log(mh1.poll()); // 10
49   console.log(mh1.poll()); // 100

最大堆完成实现

如前所述，最小堆和最大堆实现之间的唯一区别是bubbleDown和bubbleUp中的比较器。添加了与上一个示例相同的元素，即(1，10，5，100，8)，当调用poll时，max-heap 返回最高的元素。

 1   function MaxHeap() {
 2       this.items = [];
 3   }
 4   MaxHeap.prototype = Object.create(Heap.prototype); // inherit helpers from heap by copying prototype
 5   MaxHeap.prototype.poll = function() {
 6       var item = this.items[0];
 7       this.items[0] = this.items[this.items.length - 1];
 8       this.items.pop();
 9       this.bubbleDown();
10       return item;
11   }
12
13   MaxHeap.prototype.bubbleDown = function() {
14       var index = 0;
15       while (this.leftChild(index) && (this.leftChild(index) > this.items[index] ||  this.rightChild(index) > this.items[index] ) ) {
16           var biggerIndex = this.leftChildIndex(index);
17           if (this.rightChild(index) && this.rightChild(index) > this.items[bigger\Index])
18           {
19               biggerIndex = this.rightChildrenIndex(index);
20           }
21           this.swap(biggerIndex, index);
22           index = biggerIndex;
23       }
24   }
25
26   MaxHeap.prototype.bubbleUp = function() {
27       var index = this.items.length - 1;
28       while (this.parent(index) && this.parent(index) < this.items[index]) {
29           this.swap(this.parentIndex(index), index);
30           index = this.parentIndex(index);
31       }
32   }
33
34   var mh2 = new MaxHeap();
35   mh2.add(1);
36   mh2.add(10);
37   mh2.add(5);
38   mh2.add(100);
39   mh2.add(8); 

40
41   console.log(mh2.poll()); // 100
42   console.log(mh2.poll()); // 10
43   console.log(mh2.poll()); // 8
44   console.log(mh2.poll()); // 5
45   console.log(mh2.poll()); // 1

堆排序

既然已经创建了堆类，用堆进行排序就相当简单了。要获得一个排序的数组，只需在堆上调用.pop()直到它为空，并存储已存储的弹出对象。这就是所谓的堆排序。由于逾渗需要 O(log2(n))，并且排序必须弹出 n 个元素，所以堆排序的时间复杂度为 O(nlog2(n))，类似于快速排序和合并排序。

在本节中，我们将首先使用最小堆实现升序排序，然后使用最大堆实现降序排序。

升序排序(最小堆)

图 16-20 显示了当所有项目都被添加到最小堆中时的最小堆，图 16-21 到 16-23 显示了弹出项目时的堆重组。最后，当它为空时，排序完成。

img/465726_1_En_16_Fig23_HTML.jpg

图 16-23

最小堆排序:取出 12

img/465726_1_En_16_Fig22_HTML.jpg

图 16-22

最小堆排序:弹出 4

img/465726_1_En_16_Fig21_HTML.jpg

图 16-21

最小堆排序:弹出 2

img/465726_1_En_16_Fig20_HTML.jpg

图 16-20

添加所有项目后的最小堆排序

 1   var minHeapExample = new MinHeap();
 2   minHeapExample.add(12);
 3   minHeapExample.add(2);
 4   minHeapExample.add(23);
 5   minHeapExample.add(4);
 6   minHeapExample.add(13);
 7   minHeapExample.items; // [2, 4, 23, 12, 13]
 8
 9   console.log(minHeapExample.poll()); // 2
10   console.log(minHeapExample.poll()); // 4
11   console.log(minHeapExample.poll()); // 12
12   console.log(minHeapExample.poll()); // 13
13   console.log(minHeapExample.poll()); // 23

最后一个节点(原来是 13 的地方)被去掉，然后 13 被放在最上面。通过过滤过程，13 向下移动到 12 的左孩子之后，因为它比 4 和 13 都大。

降序排序(最大堆)

图 16-24 显示了所有项目都被添加到最小堆时的最大堆，图 16-25 到 16-27 显示了弹出项目时的最大堆重组。最后，当它为空时，排序完成。

img/465726_1_En_16_Fig27_HTML.jpg

图 16-27

最大排序:弹出 12 个

img/465726_1_En_16_Fig26_HTML.jpg

图 16-26

最大排序:弹出 13 个

img/465726_1_En_16_Fig25_HTML.jpg

图 16-25

最大排序:弹出 23 个

img/465726_1_En_16_Fig24_HTML.jpg

图 16-24

添加所有项目后的最大堆排序

 1   var maxHeapExample = new MaxHeap();
 2   maxHeapExample.add(12);
 3   maxHeapExample.add(2);
 4   maxHeapExample.add(23);
 5   maxHeapExample.add(4);
 6   maxHeapExample.add(13);
 7   maxHeapExample.items; // [23, 13, 12, 2, 4]
 8
 9   console.log(maxHeapExample.poll()); // 23
10   console.log(maxHeapExample.poll()); // 13
11   console.log(maxHeapExample.poll()); // 12
12   console.log(maxHeapExample.poll()); // 2
13   console.log(maxHeapExample.poll()); // 4

摘要

堆是用数组表示的树状数据结构。要获得树节点的父节点、左子节点和右子节点，可以使用表 16-1 中的索引公式。

表 16-1

堆 节点指标汇总

|

结节

|

索引

| | --- | --- | | (自己) | 普通 | | 父母 | (N-1) / 2 | | 左边的孩子 | (N2) + 1 | | 正确的孩子 | (N2) + 2 |

堆通过渗透来维持它们的结构；当一个节点被插入时，它通过重复地与元素交换来“冒泡”,直到获得合适的堆结构。对于一个最小堆，这意味着根节点中值最低的节点。对于 max-heap，这意味着根节点中值最高的节点。堆基本上是通过渗滤工作的，渗滤允许在 O(log 2 ( n ))时间内删除和插入，如表 16-2 所示。

表 16-2

堆 作战总结

|

操作

|

时间复杂度

| | --- | --- | | 删除(导致“气泡下降”) | O( 日志 2 ( n )) | | 插入(导致“冒泡”) | O( 日志 2 ( n )) | | 堆排序 | o(nlog2(n)) |

练习

你可以在 GitHub 上找到所有练习的代码。 1

跟踪数字流中的中位数

既然这个问题在这一章里，那已经是接近它的一个很大的暗示了。理论上，解决方案相当简单。有一个最小堆和一个最大堆，那么检索中间值只需要 O(1)。

例如，让我们有一个如下整数的流:12，2，23，4，13。

当插入 12 时，中位数是 12，因为这是唯一的元素。当插入 2 时，有偶数个项目:2 和 12。因此，中位数是它的算术平均值，7 ((12+2)/2)。当插入 23 时，中位数是 12。最后，当插入 13 时，中位数是 12.5，即两个中间项(12 和 13)的平均值。

1   medianH.push(12);
2   console.log(medianH.median()); // 12
3   medianH.push(2);
4   console.log(medianH.median()); // 7 ( because 12 + 2 = 14; 14/2 = 7)
5   medianH.push(23);
6   console.log(medianH.median()); // 12
7   medianH.push(13);
8   console.log(medianH.median()); // 12.5

 1   function MedianHeap() {
 2       this.minHeap = new MinHeap();
 3       this.maxHeap = new MaxHeap();
 4   }
 5
 6   MedianHeap.prototype.push = function (value) {
 7       if (value > this.median()) {
 8           this.minHeap.add(value);
 9       } else {
10           this.maxHeap.add(value);
11       }
12
13       // Re balancing
14       if (this.minHeap.size() - this.maxHeap.size() > 1) {
15           this.maxHeap.push(this.minHeap.poll());
16       }
17
18       if (this.maxHeap.size() - this.minHeap.size() > 1){
19           this.minHeap.push(this.maxHeap.poll());
20       }
21   }
22
23   MedianHeap.prototype.median = function () {
24       if (this.minHeap.size() == 0 && this.maxHeap.size() == 0){
25           return Number.NEGATIVE_INFINITY;
26       } else if (this.minHeap.size() == this.maxHeap.size()) {
27           return (this.minHeap.peek() + this.maxHeap.peek()) / 2;
28       } else if (this.minHeap.size() > this.maxHeap.size()) {
29           return this.minHeap.peek();
30       } else {
31           return this.maxHeap.peek();
32       }
33   }
34
35   var medianH = new MedianHeap();
36
37   medianH.push(12);
38   console.log(medianH.median()); // 12
39   medianH.push(2);
40   console.log(medianH.median()); // 7 ( because 12 + 2 = 14; 14/2 = 7)
41   medianH.push(23);
42   console.log(medianH.median()); // 12
43   medianH.push(13);
44   console.log(medianH.median()); // 12.5

找出数组中第 K 个最小值

这个问题之前已经在第 10 章使用 quicksort 的辅助函数探讨过了。另一种方法是使用堆。简单地将元素添加到一个堆中，并弹出第 k 次。根据最小堆的定义，这将返回数组中第 k 个最小值。

 1   var array1 = [12, 3, 13, 4, 2, 40, 23]
 2
 3   function getKthSmallestElement(array, k) {
 4       var minH = new MinHeap();
 5       for (var i = 0, arrayLength = array.length; i < arrayLength; i++) {
 6           minH.add(array[i]);
 7       }
 8       for (var i = 1; i < k; i++) {
 9           minH.poll();
10       }
11       return minH.poll();
12   }
13   getKthSmallestElement(array1, 2); // 3
14   getKthSmallestElement(array1, 1); // 2
15   getKthSmallestElement(array1, 7); // 40

找出数组中的 KTH 最大值

这与之前关于 max-heap 的想法相同。

 1   var array1 = [12,3,13,4,2,40,23];
 2
 3   function getKthBiggestElement(array, k) {
 4       var maxH = new MaxHeap();
 5       for (var i=0, arrayLength = array.length; i<arrayLength; i++) {
 6           maxH.push(array[i]);
 7       }
 8       for (var i=1; i<k; i++) {
 9           maxH.pop();
10       }
11       return maxH.pop();
12   }
13   getKthBiggestElement(array1,2); // 23
14   getKthBiggestElement(array1,1); // 40
15   getKthBiggestElement(array1,7); // 2

时间复杂度:o(klug2(n))

这里， n 是数组的大小，因为每次.pop花费 O(logT5】2(n))，要做 k 次。

空间复杂度: O( n

内存中需要 O( n )来存储堆数组。

Footnotes [1](#Fn1_source) [T2`https://github.com/Apress/js-data-structures-and-algorithms`](https://github.com/Apress/js-data-structures-and-algorithms)  

*

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/2210.html