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