 # Learn Data Structure and Algorithm in JavaScript | Part 16 Edison Pebojot(👨‍💻) Updated on ・29 min read

# Prerequisite (✋😐)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 15: Trees

01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String object’s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(❗) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(😉)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (💡).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (👀). (😃)
11 Hash Tables A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (😃)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (🔈)) not (kwewe) okay? hehehe (😅); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (😃) Let's go! (🔥🔥🔥)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (😮) There are two types of linked lists: singly (➡️) and doubly (↔️). Let’s examine the singly linked list first.(😃) Let's go! (🔥🔥🔥)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (😃)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (👍)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (😉)
19 Dynamic Programming Dynamic programming involves breaking down problems into their subproblems. Solving the subproblems and saving those results into memory to access them whenever a repeated problem needs to be solved, the algorithmic complexity decreases significantly (⬇️). To explain dynamic programming, let’s re examine the Fibonacci sequence that was discussed in Part 8. Then Part 19 will cover the rules of dynamic programming and walk you through some examples to make the concepts more concrete. (😉)
20 Bit Manipulation Bit manipulation is an advanced topic that JavaScript developers typically do not need to know. However, you should learn a bit about bit manipulation if you want to implement high-performance server-side code. Understanding bit manipulation requires some knowledge of digital logic. Any introductory course in discrete math or circuits would be helpful to understand these concepts.

# Part 16: Heaps (😱 🔥 🍡) A heap is an important data structure that returns the highest or lowest element in $O \lparen 1 \rparen$ time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.

## Understanding Heaps (🔎🍡) A heap is a tree-like data structure in which the parent is bigger (⬆️) than its children or smaller (⬇️) than its children. This property of the heap makes it useful for sorting data (📊). Heaps use an array to store data instead of having pointers to their children. In this part 16, only binary heaps will be considered. (☺️☝️)

Since a heap uses an array to store the data, the indices (🔢) of the array define the order/height of each element. A binary heap can be built by placing the first (1️⃣) array element as the root and then left (⬅️) and right (➡️) order. For example, we have the array: $[\space 2, \space 4, \space 23, \space 12, \space 13 \space]$ There are two types of binary heaps: max-heap and min-heap. In max-heap, the root node has the highest value, and each node’s value is greater than its children. In min-heap, the root node has the lowest value, and each node’s value is smaller than its children. Heaps can store any values of any type: strings, integer. This part 16 will look at heaps that store integer values only.

### Max-Heap (⬆️🔢⬆️)

A max-heap is a heap where the parent is always greater than any of its children. See the example below: Here is the array for the max-heap shown in the example above: $[ \space 100, \space 19, \space 36, \space 17, \space 3, \space 25, \space 1, \space 2, \space 7 \space ]$ .

### Min-Heap (⬇️🔢⬇️)

A min-heap is a heap where the parent is always smaller than any of its children. See the example below: Here is the array for the max-heap shown in the example above: $[ \space 1, \space 2, \space 3, \space 17, \space 19, \space 36, \space 7, \space 25, \space 100 \space]$ .

## Binary Heap Array Index Structure (🍡🔢) For a binary heap, an array is used to represent the heap by using the following indices, where N is the index of the node:

Node Index
Self $N$
Parent $\lparen N - 1 \rparen \over 2$
Left Child $\lparen N \times 2 \rparen + 1$
Right Child $\lparen N \times 2 \rparen + 2$

Figure 16-4 (below) illustrates this: Let’s first define a Heap class. An array will be used to store all the values. The following heap class implements helper functions that retrieve the parent node, the left child, and the right child. The following code block has a peek function that returns the maximum value and the minimum value.

Example:

// Heap class
function Heap () {
this.items = [];
}

// Swap
Heap.prototype.swap = function (index1, index2) {
var temp = this.items[index1];
this.items[index1] = this.items[index2];
this.items[index2] = temp;
}

// Helper Function: Return Parent Index
Heap.prototype.parentIndex = function (index) {
return Math.floor((index - 1) / 2);
}

// Helper Function: Return Left Child Index
Heap.prototype.leftChildIndex = function (index) {
return index * 2 + 1;
}

// Helper Function: Return Right Child Index
Heap.prototype.rightChildIndex = function (index) {
return index * 2 + 2;
}

// Return Parent Element
Heap.prototype.parent = function (index) {
return this.items[this.parentIndex(index)];
}

// Return Left Child Element
Heap.prototype.leftChild = function (index) {
return this.items[this.leftChildIndex(index)];
}

// Return Right Child Element
Heap.prototype.rightChild = function (index) {
return this.items[this.rightChildIndex(index)];
}

// Peek (Look)
Heap.prototype.peek = function (index) {
return this.items;
}

// Helper Function:  Return Heap (or arrray) Size
Heap.prototype.size = function () {
return this.items.length;
}


Note (📝): The size function is another helper that returns the size of the heap (in other words, the number of elements of an array).

### Percolation: Bubbling Up and Down (⬇️⬆️⬇️)

When elements are added or removed, the structure of the heap must remain (the node being greater than its children or smaller than its children). This requires items to swap and bubble up to the top of the heap.

Similar to bubbling up, some items need to bubble down to their rightful position in order to keep the structure of the heap. Percolation takes $O \lparen log_{2} \lparen n \rparen \rparen$ in time.

Let’s step through a min-heap example and insert the following values in this order: 12, 2, 23, 4, 13. Here are the steps:

Step 3: The node (2) bubbles up because it is smaller than 12 and hence should be on the top of the min-heap Step 4: Insert a new node (23) in the second child position Step 6: 12 is swapped with 4 to maintain the min-heap structure Here is the result of the array content for this heap: $[ \space 2, \space 4, \space 23, \space 12, \space 13 \space ]$

### Implementing Percolation (⬇️🔧⬆️)

To implement the percolation for min-heap structure, for bubbling down, swap the top element with one of its children if that child is smaller. Likewise, for bubbling up, swap the new element with its parent if the parent is greater than the new element.

Example:

// Heap class
function Heap () {
this.items = [];
}

// Swap
Heap.prototype.swap = function (index1, index2) {
var temp = this.items[index1];
this.items[index1] = this.items[index2];
this.items[index2] = temp;
}

// Helper Function: Return Parent Index
Heap.prototype.parentIndex = function (index) {
return Math.floor((index - 1) / 2);
}

// Helper Function: Return Left Child Index
Heap.prototype.leftChildIndex = function (index) {
return (index * 2) + 1;
}

// Helper Function: Return Right Child Index
Heap.prototype.rightChildIndex = function (index) {
return (index * 2) + 2;
}

// Return Parent Element
Heap.prototype.parent = function (index) {
return this.items[this.parentIndex(index)];
}

// Return Left Child Element
Heap.prototype.leftChild = function (index) {
return this.items[this.leftChildIndex(index)];
}

// Return Right Child Element
Heap.prototype.rightChild = function (index) {
return this.items[this.rightChildIndex(index)];
}

// Peek (Look)
Heap.prototype.peek = function (index) {
return this.items;
}

// Helper Function:  Return Heap (or arrray) Size
Heap.prototype.size = function () {
return this.items.length;
}

// Minimum Heap Class
function MinHeap () {
this.items = [];
}

// Inherit Helper Function from Heap Class By Copying Prototype
MinHeap.prototype = Object.create(Heap.prototype);

// Bubble Down
MinHeap.prototype.bubbleDown = function () {
var index = 0;
while (this.leftChild(index) && this.leftChild(index) < this.items[index]) {
var smallerIndex = this.leftChildIndex(index);
if (this.rightChild(index) && this.rightChild < this.items[smallerIndex]) {
// If right is smaller, right swaps
smallerIndex = this.rightChildIndex(index);
}
this.swap(smallerIndex, index);
index = smallerIndex;
}
}

// Bubble Up
MinHeap.prototype.bubbleUp = function () {
var index = this.items.length - 1;
while (this.parent(index) && this.parent(index) > this.items[index]) {
this.swap(this.parentIndex(index), index);
index = this.parentIndex(index);
}
}


A max-heap implementation differs only in the comparators. For bubbling down, the node swaps with one of its children if the child is greater. Likewise, for bubbling up, the newest node swaps with its parent if its parent is smaller than the new node.

### Max-Heap Example (⬆️🔢☝️)

Let’s build a max-heap now with the same values as the one used in the previous min-heap example by inserting the following values in the order: $[ \space 12, \space 2, \space 23, \space 4, \space 13 \space ]$

Step 4: The node (23) bubbles to the top to maintain max-heap structure Step 6: To maintain the max-heap structure, 4 bubbles up, and 2 bubbles down Step 8: Because of the max-heap structure, 13 and 4 swap positions Here is the result of the array content for this heap: $[ \space 23, \space 13, \space 12, \space 2, \space 4 \space ]$

## Min-Heap Complete Implementation (⬇️✅) Putting all the functions together, the complete implementation of min-heap is shown next. The add and poll functions were added. add simply adds a new element to the heap. poll removes the minimum element from the heap and calls bubbleDown to keep the min-heap order.

Full Example:

// Heap class
function Heap() {
this.items = [];
}

// Swap
Heap.prototype.swap = function (index1, index2) {
var temp = this.items[index1];
this.items[index1] = this.items[index2];
this.items[index2] = temp;
}

// Helper Function: Return Parent Index
Heap.prototype.parentIndex = function (index) {
return Math.floor((index - 1) / 2);
}

// Helper Function: Return Left Child Index
Heap.prototype.leftChildIndex = function (index) {
return (index * 2) + 1;
}

// Helper Function: Return Right Child Index
Heap.prototype.rightChildIndex = function (index) {
return (index * 2) + 2;
}

// Return Parent Element
Heap.prototype.parent = function (index) {
return this.items[this.parentIndex(index)];
}

// Return Left Child Element
Heap.prototype.leftChild = function (index) {
return this.items[this.leftChildIndex(index)];
}

// Return Right Child Element
Heap.prototype.rightChild = function (index) {
return this.items[this.rightChildIndex(index)];
}

// Peek (Look)
Heap.prototype.peek = function (index) {
return this.items;
}

// Helper Function:  Return Heap (or arrray) Size
Heap.prototype.size = function () {
return this.items.length;
}

// Minimum Heap Class
function MinHeap () {
this.items = [];
}

// Inherit Helper Function from Heap Class By Copying Prototype
MinHeap.prototype = Object.create(Heap.prototype);

this.items[this.items.length] = item;
this.bubbleUp();
}

// Poll
MinHeap.prototype.poll = function () {
var item = this.items;
this.items = this.items[this.items.length - 1];
this.items.pop();
this.bubbleDown();
return item;

}

// Bubble Down
MinHeap.prototype.bubbleDown = function () {
var index = 0;
while (this.leftChild(index) &&
(this.leftChild(index) < this.items[index] ||
this.rightChild(index) < this.items[index])) {
var smallerIndex = this.leftChildIndex(index);
if (this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) {
// If right is smaller, right swaps
smallerIndex = this.rightChildIndex(index);
}
this.swap(smallerIndex, index);
index = smallerIndex;
}
}

// Bubble Up
MinHeap.prototype.bubbleUp = function () {
var index = this.items.length - 1;
while (this.parent(index) && this.parent(index) > this.items[index]) {
this.swap(this.parentIndex(index), index);
index = this.parentIndex(index);
}
}

// Log
MinHeap.prototype.log = function () {
return [mh.poll(), mh.poll(), mh.poll(), mh.poll(), mh.poll()];
}

// Instance of the MinHeap Class
var mh = new MinHeap();

// Result
mh.log(); // Prints "[ 1, 5, 8, 10, 100 ]"

// Note: Log function is optional. I just want to show you...
// ... that the structure of array is now like this


Execution:

   // Heap class function Heap() { this.items = []; } // Swap Heap.prototype.swap = function (index1, index2) { var temp = this.items[index1]; this.items[index1] = this.items[index2]; this.items[index2] = temp; } // Helper Function: Return Parent Index Heap.prototype.parentIndex = function (index) { return Math.floor((index - 1) / 2); } // Helper Function: Return Left Child Index Heap.prototype.leftChildIndex = function (index) { return (index * 2) + 1; } // Helper Function: Return Right Child Index Heap.prototype.rightChildIndex = function (index) { return (index * 2) + 2; } // Return Parent Element Heap.prototype.parent = function (index) { return this.items[this.parentIndex(index)]; } // Return Left Child Element Heap.prototype.leftChild = function (index) { return this.items[this.leftChildIndex(index)]; } // Return Right Child Element Heap.prototype.rightChild = function (index) { return this.items[this.rightChildIndex(index)]; } // Peek (Look) Heap.prototype.peek = function (index) { return this.items; } // Helper Function: Return Heap (or arrray) Size Heap.prototype.size = function () { return this.items.length; } // Minimum Heap Class function MinHeap () { this.items = []; } // Inherit Helper Function from Heap Class By Copying Prototype MinHeap.prototype = Object.create(Heap.prototype); // Add MinHeap.prototype.add = function (item) { this.items[this.items.length] = item; this.bubbleUp(); } // Poll MinHeap.prototype.poll = function () { var item = this.items; this.items = this.items[this.items.length - 1]; this.items.pop(); this.bubbleDown(); return item; } // Bubble Down MinHeap.prototype.bubbleDown = function () { var index = 0; while (this.leftChild(index) && (this.leftChild(index) < this.items[index] || this.rightChild(index) < this.items[index])) { var smallerIndex = this.leftChildIndex(index); if (this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) { // If right is smaller, right swaps smallerIndex = this.rightChildIndex(index); } this.swap(smallerIndex, index); index = smallerIndex; } } // Bubble Up MinHeap.prototype.bubbleUp = function () { var index = this.items.length - 1; while (this.parent(index) && this.parent(index) > this.items[index]) { this.swap(this.parentIndex(index), index); index = this.parentIndex(index); } } // Log MinHeap.prototype.log = function () { return [mh.poll(), mh.poll(), mh.poll(), mh.poll(), mh.poll()]; } // Instance of the MinHeap Class var mh = new MinHeap(); // Add mh.add(1); // Add "1" mh.add(10); // Add "10" mh.add(5); // Add "5" mh.add(100); // Add "100" mh.add(8); // Add "8" // Result mh.log(); // Prints "[ 1, 5, 8, 10, 100 ]" // Note: Log function is optional. I just want to show you... // ... that the structure of array is now like this 

## Max-Heap Complete Implementation (⬆️✅) As previously discussed, the only difference between the min-heap and max-heap implementations is the comparator in bubbleDown and bubbleUp. With the same elements added as the previous example, meaning ( $\space 1, \space 10, \space 5, \space 100, \space 8 \space$ ), the max-heap returns the highest elements when poll is called.

Full Example:

// Heap class
function Heap() {
this.items = [];
}

// Swap
Heap.prototype.swap = function (index1, index2) {
var temp = this.items[index1];
this.items[index1] = this.items[index2];
this.items[index2] = temp;
}

// Helper Function: Return Parent Index
Heap.prototype.parentIndex = function (index) {
return Math.floor((index - 1) / 2);
}

// Helper Function: Return Left Child Index
Heap.prototype.leftChildIndex = function (index) {
return (index * 2) + 1;
}

// Helper Function: Return Right Child Index
Heap.prototype.rightChildIndex = function (index) {
return (index * 2) + 2;
}

// Return Parent Element
Heap.prototype.parent = function (index) {
return this.items[this.parentIndex(index)];
}

// Return Left Child Element
Heap.prototype.leftChild = function (index) {
return this.items[this.leftChildIndex(index)];
}

// Return Right Child Element
Heap.prototype.rightChild = function (index) {
return this.items[this.rightChildIndex(index)];
}

// Peek (Look)
Heap.prototype.peek = function (index) {
return this.items;
}

// Helper Function:  Return Heap (or arrray) Size
Heap.prototype.size = function () {
return this.items.length;
}

// Minimum Heap Class
function MaxHeap () {
this.items = [];
}

// Inherit Helper Function from Heap Class By Copying Prototype
MaxHeap.prototype = Object.create(Heap.prototype);

this.items[this.items.length] = item;
this.bubbleUp();
}

// Poll
MaxHeap.prototype.poll = function () {
var item = this.items;
this.items = this.items[this.items.length - 1];
this.items.pop();
this.bubbleDown();
return item;

}

// Bubble Down
MaxHeap.prototype.bubbleDown = function () {
var index = 0;
while (this.leftChild(index) &&
(this.leftChild(index) > this.items[index] ||
this.rightChild(index) > this.items[index])) {
var biggerIndex = this.leftChildIndex(index);
if (this.rightChild(index) && this.rightChild(index) > this.items[biggerIndex]) {
// If right is smaller, right swaps
biggerIndex = this.rightChildIndex(index);
}
this.swap(biggerIndex, index);
index = biggerIndex;
}
}

// Bubble Up
MaxHeap.prototype.bubbleUp = function () {
var index = this.items.length - 1;
while (this.parent(index) && this.parent(index) < this.items[index]) {
this.swap(this.parentIndex(index), index);
index = this.parentIndex(index);
}
}

// Log
MaxHeap.prototype.log = function () {
return [mh.poll(), mh.poll(), mh.poll(), mh.poll(), mh.poll()];
}

// Instance of the MaxHeap Class
var mh = new MaxHeap();

// Result
mh.log(); // Prints "[ 100, 10, 8, 5, 1 ]"

// Note: Log function is optional. I just want to show you...
// ... that the structure of array is now like this


Execution:

   // Heap class function Heap() { this.items = []; } // Swap Heap.prototype.swap = function (index1, index2) { var temp = this.items[index1]; this.items[index1] = this.items[index2]; this.items[index2] = temp; } // Helper Function: Return Parent Index Heap.prototype.parentIndex = function (index) { return Math.floor((index - 1) / 2); } // Helper Function: Return Left Child Index Heap.prototype.leftChildIndex = function (index) { return (index * 2) + 1; } // Helper Function: Return Right Child Index Heap.prototype.rightChildIndex = function (index) { return (index * 2) + 2; } // Return Parent Element Heap.prototype.parent = function (index) { return this.items[this.parentIndex(index)]; } // Return Left Child Element Heap.prototype.leftChild = function (index) { return this.items[this.leftChildIndex(index)]; } // Return Right Child Element Heap.prototype.rightChild = function (index) { return this.items[this.rightChildIndex(index)]; } // Peek (Look) Heap.prototype.peek = function (index) { return this.items; } // Helper Function: Return Heap (or arrray) Size Heap.prototype.size = function () { return this.items.length; } // Minimum Heap Class function MaxHeap () { this.items = []; } // Inherit Helper Function from Heap Class By Copying Prototype MaxHeap.prototype = Object.create(Heap.prototype); // Add MaxHeap.prototype.add = function (item) { this.items[this.items.length] = item; this.bubbleUp(); } // Poll MaxHeap.prototype.poll = function () { var item = this.items; this.items = this.items[this.items.length - 1]; this.items.pop(); this.bubbleDown(); return item; } // Bubble Down MaxHeap.prototype.bubbleDown = function () { var index = 0; while (this.leftChild(index) && (this.leftChild(index) > this.items[index] || this.rightChild(index) > this.items[index])) { var biggerIndex = this.leftChildIndex(index); if (this.rightChild(index) && this.rightChild(index) > this.items[biggerIndex]) { // If right is smaller, right swaps biggerIndex = this.rightChildIndex(index); } this.swap(biggerIndex, index); index = biggerIndex; } } // Bubble Up MaxHeap.prototype.bubbleUp = function () { var index = this.items.length - 1; while (this.parent(index) && this.parent(index) < this.items[index]) { this.swap(this.parentIndex(index), index); index = this.parentIndex(index); } } // Log MaxHeap.prototype.log = function () { return [mh.poll(), mh.poll(), mh.poll(), mh.poll(), mh.poll()]; } // Instance of the MaxHeap Class var mh = new MaxHeap(); // Add mh.add(1); // Add "1" mh.add(10); // Add "10" mh.add(5); // Add "5" mh.add(100); // Add "100" mh.add(8); // Add "8" // Result mh.log(); // Prints "[ 100, 10, 8, 5, 1 ]" // Note: Log function is optional. I just want to show you... // ... that the structure of array is now like this 

## Heap Sort (🍡📊) Now that heap classes have been created, sorting with a heap is fairly straightforward. To get a sorted array, simply call .pop() on the heap until it is empty and store the stored popped objects. This is as known as a heap sort. Since percolation takes $O \lparen log_{2} \lparen n \rparen \rparen$ , and sorting must pop $n$ number of elements, the time complexity for a heap sort is $O \lparen nlog_{2} \lparen n \rparen \rparen$ , like quicksort and mergesort.

Reminder (💡): In this section, we will do an ascending sort using a min-heap and a descending sort using a max-heap.

### Ascending-Order Sort (Min-Heap) (⬇️➡️📊)

Figure 16-20 shows the min-heap when all the items have been added: And Figures 16-21 to 16-23 show the heap restructuring as items are popped. Finally, when it is empty, the sort is complete:   Let's code the example above:

// Heap class
function Heap() {
this.items = [];
}

// Swap
Heap.prototype.swap = function (index1, index2) {
var temp = this.items[index1];
this.items[index1] = this.items[index2];
this.items[index2] = temp;
}

// Helper Function: Return Parent Index
Heap.prototype.parentIndex = function (index) {
return Math.floor((index - 1) / 2);
}

// Helper Function: Return Left Child Index
Heap.prototype.leftChildIndex = function (index) {
return (index * 2) + 1;
}

// Helper Function: Return Right Child Index
Heap.prototype.rightChildIndex = function (index) {
return (index * 2) + 2;
}

// Return Parent Element
Heap.prototype.parent = function (index) {
return this.items[this.parentIndex(index)];
}

// Return Left Child Element
Heap.prototype.leftChild = function (index) {
return this.items[this.leftChildIndex(index)];
}

// Return Right Child Element
Heap.prototype.rightChild = function (index) {
return this.items[this.rightChildIndex(index)];
}

// Peek (Look)
Heap.prototype.peek = function (index) {
return this.items;
}

// Helper Function:  Return Heap (or arrray) Size
Heap.prototype.size = function () {
return this.items.length;
}

// Minimum Heap Class
function MinHeap () {
this.items = [];
}

// Inherit Helper Function from Heap Class By Copying Prototype
MinHeap.prototype = Object.create(Heap.prototype);

this.items[this.items.length] = item;
this.bubbleUp();
}

// Poll
MinHeap.prototype.poll = function () {
var item = this.items;
this.items = this.items[this.items.length - 1];
this.items.pop();
this.bubbleDown();
return item;

}

// Bubble Down
MinHeap.prototype.bubbleDown = function () {
var index = 0;
while (this.leftChild(index) &&
(this.leftChild(index) < this.items[index] ||
this.rightChild(index) < this.items[index])) {
var smallerIndex = this.leftChildIndex(index);
if (this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) {
// If right is smaller, right swaps
smallerIndex = this.rightChildIndex(index);
}
this.swap(smallerIndex, index);
index = smallerIndex;
}
}

// Bubble Up
MinHeap.prototype.bubbleUp = function () {
var index = this.items.length - 1;
while (this.parent(index) && this.parent(index) > this.items[index]) {
this.swap(this.parentIndex(index), index);
index = this.parentIndex(index);
}
}

// Log
MinHeap.prototype.log = function () {
return [mh.poll(), mh.poll(), mh.poll(), mh.poll(), mh.poll()];
}

// Instance of the MinHeap Class
var mh = new MinHeap();

// Before
console.log(mh.items); // Prints "[ 2, 4, 23, 12, 13 ]"

// After
mh.log(); // Prints "[ 2, 4, 12, 13, 23 ]"

// Note: Log function is optional. I just want to show you...
// ... that the structure of array is now like this


Execution:

   // Heap class function Heap() { this.items = []; } // Swap Heap.prototype.swap = function (index1, index2) { var temp = this.items[index1]; this.items[index1] = this.items[index2]; this.items[index2] = temp; } // Helper Function: Return Parent Index Heap.prototype.parentIndex = function (index) { return Math.floor((index - 1) / 2); } // Helper Function: Return Left Child Index Heap.prototype.leftChildIndex = function (index) { return (index * 2) + 1; } // Helper Function: Return Right Child Index Heap.prototype.rightChildIndex = function (index) { return (index * 2) + 2; } // Return Parent Element Heap.prototype.parent = function (index) { return this.items[this.parentIndex(index)]; } // Return Left Child Element Heap.prototype.leftChild = function (index) { return this.items[this.leftChildIndex(index)]; } // Return Right Child Element Heap.prototype.rightChild = function (index) { return this.items[this.rightChildIndex(index)]; } // Peek (Look) Heap.prototype.peek = function (index) { return this.items; } // Helper Function: Return Heap (or arrray) Size Heap.prototype.size = function () { return this.items.length; } // Minimum Heap Class function MinHeap () { this.items = []; } // Inherit Helper Function from Heap Class By Copying Prototype MinHeap.prototype = Object.create(Heap.prototype); // Add MinHeap.prototype.add = function (item) { this.items[this.items.length] = item; this.bubbleUp(); } // Poll MinHeap.prototype.poll = function () { var item = this.items; this.items = this.items[this.items.length - 1]; this.items.pop(); this.bubbleDown(); return item; } // Bubble Down MinHeap.prototype.bubbleDown = function () { var index = 0; while (this.leftChild(index) && (this.leftChild(index) < this.items[index] || this.rightChild(index) < this.items[index])) { var smallerIndex = this.leftChildIndex(index); if (this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) { // If right is smaller, right swaps smallerIndex = this.rightChildIndex(index); } this.swap(smallerIndex, index); index = smallerIndex; } } // Bubble Up MinHeap.prototype.bubbleUp = function () { var index = this.items.length - 1; while (this.parent(index) && this.parent(index) > this.items[index]) { this.swap(this.parentIndex(index), index); index = this.parentIndex(index); } } // Log MinHeap.prototype.log = function () { return [mh.poll(), mh.poll(), mh.poll(), mh.poll(), mh.poll()]; } // Instance of the MinHeap Class var mh = new MinHeap(); // Add mh.add(12); // Add "12" mh.add(2); // Add "2" mh.add(23); // Add "23" mh.add(4); // Add "4" mh.add(13); // Add "13" // Before console.log(mh.items); // Prints "[ 2, 4, 23, 12, 13 ]" // After mh.log(); // Prints "[ 2, 4, 12, 13, 23 ]" // Note: Log function is optional. I just want to show you... // ... that the structure of array is now like this 

Note (📝): Through the percolation process, 23 moves down since it’s bigger than both 4 and 13.

### Descending-Order Sort (Max-Heap) (⬆️⬅️📊)

Figure 16-24 shows the max-heap when all the items have been added: And Figures 16-25 through 16-27 show the max-heap restructuring as items are popped. Finally, when it is empty, the sort is complete:   Let's code the example above:

// Heap class
function Heap() {
this.items = [];
}

// Swap
Heap.prototype.swap = function (index1, index2) {
var temp = this.items[index1];
this.items[index1] = this.items[index2];
this.items[index2] = temp;
}

// Helper Function: Return Parent Index
Heap.prototype.parentIndex = function (index) {
return Math.floor((index - 1) / 2);
}

// Helper Function: Return Left Child Index
Heap.prototype.leftChildIndex = function (index) {
return (index * 2) + 1;
}

// Helper Function: Return Right Child Index
Heap.prototype.rightChildIndex = function (index) {
return (index * 2) + 2;
}

// Return Parent Element
Heap.prototype.parent = function (index) {
return this.items[this.parentIndex(index)];
}

// Return Left Child Element
Heap.prototype.leftChild = function (index) {
return this.items[this.leftChildIndex(index)];
}

// Return Right Child Element
Heap.prototype.rightChild = function (index) {
return this.items[this.rightChildIndex(index)];
}

// Peek (Look)
Heap.prototype.peek = function (index) {
return this.items;
}

// Helper Function:  Return Heap (or arrray) Size
Heap.prototype.size = function () {
return this.items.length;
}

// Minimum Heap Class
function MaxHeap () {
this.items = [];
}

// Inherit Helper Function from Heap Class By Copying Prototype
MaxHeap.prototype = Object.create(Heap.prototype);

this.items[this.items.length] = item;
this.bubbleUp();
}

// Poll
MaxHeap.prototype.poll = function () {
var item = this.items;
this.items = this.items[this.items.length - 1];
this.items.pop();
this.bubbleDown();
return item;

}

// Bubble Down
MaxHeap.prototype.bubbleDown = function () {
var index = 0;
while (this.leftChild(index) &&
(this.leftChild(index) > this.items[index] ||
this.rightChild(index) > this.items[index])) {
var biggerIndex = this.leftChildIndex(index);
if (this.rightChild(index) && this.rightChild(index) > this.items[biggerIndex]) {
// If right is smaller, right swaps
biggerIndex = this.rightChildIndex(index);
}
this.swap(biggerIndex, index);
index = biggerIndex;
}
}

// Bubble Up
MaxHeap.prototype.bubbleUp = function () {
var index = this.items.length - 1;
while (this.parent(index) && this.parent(index) < this.items[index]) {
this.swap(this.parentIndex(index), index);
index = this.parentIndex(index);
}
}

// Log
MaxHeap.prototype.log = function () {
return [mh.poll(), mh.poll(), mh.poll(), mh.poll(), mh.poll()];
}

// Instance of the MaxHeap Class
var mh = new MaxHeap();

// Before
console.log(mh.items); // Prints "[ 2, 4, 23, 12, 13 ]"

// After
mh.log(); // Prints "[ 23, 13, 12, 4, 2 ]"

// Note: Log function is optional. I just want to show you...
// ... that the structure of array is now like this


Execution:

   // Heap class function Heap() { this.items = []; } // Swap Heap.prototype.swap = function (index1, index2) { var temp = this.items[index1]; this.items[index1] = this.items[index2]; this.items[index2] = temp; } // Helper Function: Return Parent Index Heap.prototype.parentIndex = function (index) { return Math.floor((index - 1) / 2); } // Helper Function: Return Left Child Index Heap.prototype.leftChildIndex = function (index) { return (index * 2) + 1; } // Helper Function: Return Right Child Index Heap.prototype.rightChildIndex = function (index) { return (index * 2) + 2; } // Return Parent Element Heap.prototype.parent = function (index) { return this.items[this.parentIndex(index)]; } // Return Left Child Element Heap.prototype.leftChild = function (index) { return this.items[this.leftChildIndex(index)]; } // Return Right Child Element Heap.prototype.rightChild = function (index) { return this.items[this.rightChildIndex(index)]; } // Peek (Look) Heap.prototype.peek = function (index) { return this.items; } // Helper Function: Return Heap (or arrray) Size Heap.prototype.size = function () { return this.items.length; } // Minimum Heap Class function MaxHeap () { this.items = []; } // Inherit Helper Function from Heap Class By Copying Prototype MaxHeap.prototype = Object.create(Heap.prototype); // Add MaxHeap.prototype.add = function (item) { this.items[this.items.length] = item; this.bubbleUp(); } // Poll MaxHeap.prototype.poll = function () { var item = this.items; this.items = this.items[this.items.length - 1]; this.items.pop(); this.bubbleDown(); return item; } // Bubble Down MaxHeap.prototype.bubbleDown = function () { var index = 0; while (this.leftChild(index) && (this.leftChild(index) > this.items[index] || this.rightChild(index) > this.items[index])) { var biggerIndex = this.leftChildIndex(index); if (this.rightChild(index) && this.rightChild(index) > this.items[biggerIndex]) { // If right is smaller, right swaps biggerIndex = this.rightChildIndex(index); } this.swap(biggerIndex, index); index = biggerIndex; } } // Bubble Up MaxHeap.prototype.bubbleUp = function () { var index = this.items.length - 1; while (this.parent(index) && this.parent(index) < this.items[index]) { this.swap(this.parentIndex(index), index); index = this.parentIndex(index); } } // Log MaxHeap.prototype.log = function () { return [mh.poll(), mh.poll(), mh.poll(), mh.poll(), mh.poll()]; } // Instance of the MaxHeap Class var mh = new MaxHeap(); // Add mh.add(12); // Add "12" mh.add(2); // Add "2" mh.add(23); // Add "23" mh.add(4); // Add "4" mh.add(13); // Add "13" // Before console.log(mh.items); // Prints "[ 2, 4, 23, 12, 13 ]" // After mh.log(); // Prints "[ 23, 13, 12, 4, 2 ]" // Note: Log function is optional. I just want to show you... // ... that the structure of array is now like this 

## Summary (📚📚) A heap is a tree-like data structure represented using arrays. To get the parent, left child, and right child, you can use the index formula in Table 16-1.

Heaps maintain their structure via percolation; when a node is inserted, it bubbles up by swapping elements until the proper heap structure is achieved. For a min-heap, this means the lowest-valued node at the root. For a max-heap, this means the highest-valued node at the root. Heaps work fundamentally by percolation, which allows deletion and insertion in $O \lparen log_{2} \lparen n \rparen \rparen$ time, as summarized in Table 16-2.

# Up Next👉 Part 17: Graphs (🔥🔥) (September 12-13, 2020) ### Discussion   