MinHeap, MaxHeap and heapSort implementation in JavaScript
npm install @kartjim/heap> 堆 在大部分编程语言中,都已经有内置方法实现它,但似乎JS并没有。
>
> 最大堆和最小堆:用于高效快速地取得当前数据集中最大或者最小的元素
> The default initial size of heap is 0.
sh
npm i @kartjim/heap
`
require
`js
const {
MaxHeap,
MinHeap,
minHeapSort,
maxHeapSort
} = require('@kartjim/heap');
`import
`js
import {
MaxHeap,
MinHeap,
minHeapSort,
maxHeapSort
} from '@kartjim/heap';
`HeapSort
$3
> sort the array using MaxHeap (from maximum to minimum).`js
const arr = [12, 668, 1, 0, 4, 67];
maxHeapSort(arr) // [668, 67, 12, 4, 1, 0]
`
$3
> sort the array using MaxHeap (from minimum to maximum).`js
const arr = [12, 668, 1, 0, 4, 67];
minHeapSort(arr) // [0, 1, 4, 12, 67, 668]
`MaxHeap API
$3
constructor 时间复杂度: $O(N)$
空间复杂度: $O(N)$
`js
const heap = new MaxHeap(4);
`$3
> add a new element to the MaxHeap. 时间复杂度: $O(log N)$
空间复杂度: $O(1)$
`js
heap.push(1);
heap.push(2);
heap.push(3);
`$3
> return the max element in the MaxHeap. 时间复杂度: $O(1)$。
空间复杂度: $O(1)$。
`js
heap.peek() // 3
`$3
> remove the max element in the MaxHeap. 时间复杂度: $O(log N)$
空间复杂度: $O(1)$
`js
heap.pop() // 3
`$3
> return the size of the MaxHeap.`js
heap.getSize() // 2
`
$3
> check if the MaxHeap is empty`js
heap.isEmpty() // false
`
$3
> create a MaxHeap from a Array.`js
const t = MaxHeap.heapify([1, 2, 3, 4]);
t.peek() // 4
`MinHeap API
$3
constructor 时间复杂度: $O(N)$
空间复杂度: $O(N)$
`js
const heap = new MinHeap(4);
`$3
> add a new element to the MinHeap. 时间复杂度: $O(log N)$
空间复杂度: $O(1)$
`js
heap.push(1);
heap.push(2);
heap.push(3);
`$3
> return the max element in the MinHeap. 时间复杂度: $O(1)$。
空间复杂度: $O(1)$。
`js
heap.peek() // 1
`$3
> remove the max element in the MinHeap. 时间复杂度: $O(log N)$
空间复杂度: $O(1)$
`js
heap.pop() // 1
`$3
> return the size of the MinHeap.`js
heap.getSize() // 2
`
$3
> check if the MinHeap is empty`js
heap.isEmpty() // false
`
$3
> create a MinHeap from a Array.`js
const t = MaxHeap.heapify([1, 2, 3, 4]);
t.peek() // 1
``