Heap (data-structure)

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property described below.

In a min heap, if P is a parent node of C, then the key (the value) of P is less than or equal to the key of C.

Made with okso.app

In a max heap, the key of P is greater than or equal to the key of C

The node at the "top" of the heap with no parents is called the root node.

Time Complexities

Here are time complexities of various heap data structures. Function names assume a max-heap.

Operation	find-max	delete-max	insert	increase-key	meld
Binary	`Θ(1)`	`Θ(log n)`	`O(log n)`	`O(log n)`	`Θ(n)`
Leftist	`Θ(1)`	`Θ(log n)`	`Θ(log n)`	`O(log n)`	`Θ(log n)`
Binomial	`Θ(1)`	`Θ(log n)`	`Θ(1)`	`O(log n)`	`O(log n)`
Fibonacci	`Θ(1)`	`Θ(log n)`	`Θ(1)`	`Θ(1)`	`Θ(1)`
Pairing	`Θ(1)`	`Θ(log n)`	`Θ(1)`	`o(log n)`	`Θ(1)`
Brodal	`Θ(1)`	`Θ(log n)`	`Θ(1)`	`Θ(1)`	`Θ(1)`
Rank-pairing	`Θ(1)`	`Θ(log n)`	`Θ(1)`	`Θ(1)`	`Θ(1)`
Strict Fibonacci	`Θ(1)`	`Θ(log n)`	`Θ(1)`	`Θ(1)`	`Θ(1)`
2-3 heap	`O(log n)`	`O(log n)`	`O(log n)`	`Θ(1)`	`?`

Where:

find-max (or find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively (a.k.a. peek)
delete-max (or delete-min): removing the root node of a max heap (or min heap), respectively
insert: adding a new key to the heap (a.k.a., push)
increase-key or decrease-key: updating a key within a max- or min-heap, respectively
meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.

In this repository, the MaxHeap.js and MinHeap.js are examples of the Binary heap.