Skip to content

Latest commit

 

History

History
 
 

Heap (data-structure)

Read this in other languages: 简体中文, Русский, 日本語, Français, Português, Türkçe, 한국어, Українська

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.

MinHeap

Made with okso.app

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

MaxHeap

Array Representation

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.

Implementation

  • 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).

References