Heap

Definition

A heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap). Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort.

Source: Wikipedia

Code: https://github.com/felipernb/algorithms.js/blob/master/data_structures/heap.js

Tests: https://github.com/felipernb/algorithms.js/blob/master/test/data_structures/heap.js

How to use

Import

var Heap = require('algorithms').DataStructure.Heap;

Initialization

MaxHeap

var maxHeap = new Heap.MaxHeap();

MinHeap

var minHeap = new Heap.MinHeap();

Heap.prototype.insert(n)

Insert the element into the heap, in O(lg n)

maxHeap.insert(4);
maxHeap.insert(10);
maxHeap.insert(5);

/**
 * Will give you a heap like:
 *     4
 * 10     5
 *
 * Or, represented as the array: [4, 10, 5]
 */

Heap.prototype.isEmpty()

Boolean indicating whether the heap is empty

var maxHeap = new Heap.MaxHeap();
heap.isEmpty(); // true
maxHeap.insert(4);
heap.isEmpty(); // false

Heap.prototype.extract()

Extracts the minimum element from the MinHeap, or the maximum element from the MaxHeap

MinHeap

var minHeap = new Heap.MinHeap();
minHeap.insert(200);
minHeap.insert(0);
minHeap.insert(10);
minHeap.insert(3);

minHeap.extract(); // 0
minHeap.extract(); // 3
minHeap.extract(); // 10
minHeap.extract(); // 200

MaxHeap

var maxHeap = new Heap.MaxHeap();
maxHeap.insert(200);
maxHeap.insert(0);
maxHeap.insert(10);
maxHeap.insert(3);

minHeap.extract(); // 200
minHeap.extract(); // 10
minHeap.extract(); // 3
minHeap.extract(); // 0

Heap.prototype.heapify(array)

Initializes a heap with the elements in the array

var maxHeap = new Heap.MaxHeap();
maxHeap.heapify([10, 2091, 4, 1, 5, 500, 0, 18, 3, 22, 20]);
maxHeap.extract(); // 2091
maxHeap.extract(); // 500
maxHeap.extract(); // 22
maxHeap.extract(); // 20
maxHeap.extract(); // 18
maxHeap.extract(); // 10
maxHeap.extract(); // 5
maxHeap.extract(); // 4
maxHeap.extract(); // 3
maxHeap.extract(); // 1
maxHeap.extract(); // 0