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.

MaxHeap.js and MinHeap.js
MaxHeapAdhoc.js and MinHeapAdhoc.js - The minimalistic (ad hoc) version of a MinHeap/MaxHeap data structure that doesn't have external dependencies and that is easy to copy-paste and use during the coding interview if allowed by the interviewer (since many data structures in JS are missing).