@kartjim/heap

1.1.1 • Public • Published

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

Package Sidebar

Install

npm i @kartjim/heap

Weekly Downloads

1

Version

1.1.1

License

MIT

Unpacked Size

11.5 kB

Total Files

8

Last publish

Collaborators

  • kartjim