loading...
Cover image for Learn Data Structure and Algorithm in JavaScript | Part 16

Learn Data Structure and Algorithm in JavaScript | Part 16

edisonnpebojot profile image 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

Part Table of Contents Description
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 (😱 🔥 🍡)

Alt Text

A heap is an important data structure that returns the highest or lowest element in O(1)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 (🔎🍡)

Alt text

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: [ 2, 4, 23, 12, 13 ][\space 2, \space 4, \space 23, \space 12, \space 13 \space]

Alt Text

Figure 16-1. Heap indices

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:

Alt Text

Figure 16-2. Max-heap

Here is the array for the max-heap shown in the example above: [ 100, 19, 36, 17, 3, 25, 1, 2, 7 ][ \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:

Alt Text

Figure 16-3. Min-heap

Here is the array for the max-heap shown in the example above: [ 1, 2, 3, 17, 19, 36, 7, 25, 100 ][ \space 1, \space 2, \space 3, \space 17, \space 19, \space 36, \space 7, \space 25, \space 100 \space] .

Binary Heap Array Index Structure (🍡🔢)

Alt text

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 NN
Parent (N1)2\lparen N - 1 \rparen \over 2
Left Child (N×2)+1\lparen N \times 2 \rparen + 1
Right Child (N×2)+2\lparen N \times 2 \rparen + 2

Figure 16-4 (below) illustrates this:

Alt Text

Figure 16-4. Heap relationship

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[0];
}

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

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(log2(n))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 1: Insert 12 as the first node
Alt Text

Figure 16-5. The min-heap root node

Step 2: Insert a new node (2)
Alt Text

Figure 16-6. The newest node is smaller than the parent

Step 3: The node (2) bubbles up because it is smaller than 12 and hence should be on the top of the min-heap
Alt Text

Figure 16-7. The smaller node has bubbled up to the parent position

Step 4: Insert a new node (23) in the second child position
Alt Text

Figure 16-8. The larger 23 node remains in place in the min-heap structure

Step 5: Insert 4 in the heap
Alt Text

Figure 16-9. The new node in the min-heap is smaller than the one above it

Step 6: 12 is swapped with 4 to maintain the min-heap structure
Alt Text

Figure 16-10. The smaller 4 node has bubbled up to maintain the min-heap structure

Step 7: Insert 13
Alt Text

Figure 16-11. The newest and larger node (13) remains in place

Here is the result of the array content for this heap: [ 2, 4, 23, 12, 13 ][ \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[0];
}

// 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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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: [ 12, 2, 23, 4, 13 ][ \space 12, \space 2, \space 23, \space 4, \space 13 \space ]

Step 1: Insert the first node, which is 12
Alt Text

Figure 16-12. The first max-heap node

Step 2: Insert a new node (2)
Alt Text

Figure 16-13. The new smaller node remains in place in the max-heap structure

Step 3: Insert 23
Alt Text

Figure 16-14. The new child node is larger than the parent

Step 4: The node (23) bubbles to the top to maintain max-heap structure
Alt Text

Figure 16-15. The new larger node is swapped with the smaller 12

Step 5: Insert 4
Alt Text

Figure 16-16. The new node is larger than the one above it

Step 6: To maintain the max-heap structure, 4 bubbles up, and 2 bubbles down
Alt Text

Figure 16-17. The 4 and 2 nodes swap places

Step 7: Insert 13
Alt Text

Figure 16-18. The new node is larger than the one above it

Step 8: Because of the max-heap structure, 13 and 4 swap positions
Alt Text

Figure 16-19. Percolation restores the max-heap structure

Here is the result of the array content for this heap: [ 23, 13, 12, 2, 4 ][ \space 23, \space 13, \space 12, \space 2, \space 4 \space ]

Min-Heap Complete Implementation (⬇️✅)

Alt text
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[0];
}

// 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[0];
    this.items[0] = 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
Enter fullscreen mode Exit fullscreen mode

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[0]; } // 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[0]; this.items[0] = 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 (⬆️✅)

Alt text

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 (  1, 10, 5, 100, 8 \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[0];
}

// 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[0];
    this.items[0] = 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
Enter fullscreen mode Exit fullscreen mode

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[0]; } // 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[0]; this.items[0] = 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 (🍡📊)

Alt text

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(log2(n))O \lparen log_{2} \lparen n \rparen \rparen , and sorting must pop nn number of elements, the time complexity for a heap sort is O(nlog2(n))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:

Alt Text

Figure 16-20. Min-heap sort after all items 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:

Alt Text

Figure 16-21. Min-heap sort: popping 2 out

Alt Text

Figure 16-22. Min-heap sort: popping 4 out

Alt Text

Figure 16-23. Min-heap sort: popping 12 out

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[0];
}

// 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[0];
    this.items[0] = 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
Enter fullscreen mode Exit fullscreen mode

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[0]; } // 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[0]; this.items[0] = 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:

Alt Text

Figure 16-24. Max-heap sort after all items are 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:

Alt Text

Figure 16-25. Max sort: popping 23 out

Alt Text

Figure 16-26. Max sort: popping 13 out

Alt Text

Figure 16-27. Max sort: popping 12 out

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[0];
}

// 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[0];
    this.items[0] = 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
Enter fullscreen mode Exit fullscreen mode

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[0]; } // 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[0]; this.items[0] = 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 (📚📚)

Alt text

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.

Node Index
Self NN
Parent (N1)2\lparen N - 1 \rparen \over 2
Left Child (N×2)+1\lparen N \times 2 \rparen + 1
Right Child (N×2)+2\lparen N \times 2 \rparen + 2
Table 16-1. Heap Node Index Summary

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(log2(n))O \lparen log_{2} \lparen n \rparen \rparen time, as summarized in Table 16-2.

Operation Time Complexity
Deletion (leads to “bubble down”) O(log2(n))O \lparen log_{2} \lparen n \rparen \rparen
Insertion (leads to “bubble up”) O(log2(n))O \lparen log_{2} \lparen n \rparen \rparen
Heap sort O(n log2(n))O \lparen n \space log_{2} \lparen n \rparen \rparen
Table 16-2. Heap Operations Summary

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


Alt Text

Posted on by:

edisonnpebojot profile

Edison Pebojot(👨‍💻)

@edisonnpebojot

I started using computers and writing software around 2008 and 2009, I taught myself Programming. However, I wasn't a typical "nerd-klutz". 😅

Discussion

pic
Editor guide