preface
Binary heap is a very famous data structure in computer science. It is often used in priority queue and heap sorting algorithm because it can find maximum and minimum values efficiently and quickly.
This article explains how binary heaps are implemented in TypeScript. Interested developers are welcome to read this article.
Writing in the front
This article focuses on how to implement heaps. For developers unfamiliar with the data structure of heaps, please refer to my other article: Data Structures: Heaps
Implementation approach
Binary heap is a special binary tree, binary heap is also called heap, it has the following two characteristics:
- It’s a complete binary tree
- A binary heap is either the smallest heap or the largest heap
Complete binary tree
A complete binary tree in which each layer has left and right children (except for the leaves of the last layer), and the leaves of the last layer are, as far as possible, left children.
The following diagram depicts a complete binary tree:
Minimum heap and maximum heap
- Minimum heap: All nodes are less than or equal to their children
- Maximum heap: All nodes are greater than or equal to their children
The following figure depicts the maximum heap and minimum heap
Implement binary heap
Binary heap can be represented in two ways:
- Represented by nodes like a binary tree
- Use array representation to retrieve values of parent, left, and right nodes by index value
The following figure illustrates two different representations
Operational heap node
We use arrays to represent binary heaps. For a node at a given position (index), we can do the following:
- Gets the left child node position of the given node: 2 * index + 1
- Get the position of the right child node of the given node: 2 * index + 2
- Gets the parent position of the given node :(index-1) / 2
Insert data into the heap
Insert into the heap refers to inserting data into the bottom leaf of the heap and siftUp, which means that we will swap the data with its parent until the parent is less than the inserted value.
- The INSERT method takes one parameter: the data to insert
- A non-null check is required on the inserted data, or false if null is returned
- Appending the data to be inserted to the end of the heap when the data is not empty
- After the insertion is complete, perform the siftUp operation to move the data to the appropriate location
- When the move is complete, it successfully inserted a piece of data into the heap, returning true
The implementation of the move up operation is as follows:
- The siftUp method takes a single parameter: the index of the inserted data.
- Gets the location of the parent node to insert data into.
- Swap nodes whose index is greater than 0 and whose heap[parent] > heap[index]
- Update index and parent, continue node swapping until heap[parent] < heap[index]
The implementation of the exchange is as follows:
- Swap takes three arguments: the array to operate on, the location of the element swapped, and the location of the element swapped
- Declare a temporary variable temp and assign the exchanged element
- The swapped element is assigned to the swapped element
- The swapped element is assigned the value temp
Next we use an example to illustrate the above insert process, as shown in the figure below for a minimum heap, where we insert a new node 2.
- Find its parent node 12, compare the size of 12 with that of 2, 12 > 2, and swap positions
- In this case, the parent of 2 is 5, which is greater than 2
- 2 the parent of 2 is 1,1 < 2, and the insert is complete
Find the maximum or minimum value in the heap
- The zero element of the array in the minimum heap is the minimum of the heap
- The zero element of the array in the maximum heap is the maximum of the heap
Export the minimum or maximum value in the heap
Removing the minimum (minimum heap) or maximum (maximum heap) means removing the first element in the array (the root of the heap).
After removal, we need to move the last element of the heap to the root and perform the siftDown function, which means we will swap elements until the heap is structurally sound.
- The extract function does not accept arguments
- Returns undefined if the heap is empty
- If the heap length is 1, return the top element directly
- Otherwise, declare a variable to hold the heap-top element
- Perform a drop function to adjust the heap structure
- Returns the top element of the saved heap
Implementation of the move down operation:
- The siftDown function takes one argument: the position of the element to be adjusted (index)
- Declare a variable (Element) to hold index
- Index (left, right, heap size);
- If heap[element] > heap[left], update element’s value to left
- If heap[element] > heap[right], update element’s value to right
- If the index! If == element, the index and element positions are swapped, continuing with the siftDown function
Next, we illustrate the above implementation with an example of a minimum heap
- We export the top of the heap node 1
- At this point, we need to put the last node of the heap on top of the heap
- At this point, move down to compare the size of 12 with its left child node 2, 12 > 2, and switch node position
- Continue the move down operation, compare the size of 12 with its left child node 5, 12 > 5, switch node position
- Index === element, the move down operation is complete, and the heap node is exported
Implement maximum heap
The above operation has realized a minimum heap, the difference between the maximum heap and the minimum heap lies in the comparison of nodes, so we only need to inherit the minimum heap, rewrite the comparison function, the original a and B comparison, b and A can be compared.
The implementation code
Above we explained the concept of heap, analysis of the implementation ideas, next we will be the above implementation ideas into code
- Create the heap. ts file
- Declare the MinHeap class, declare the heap, compare the function, initialize the heap
export class MinHeap<T> {
// Use arrays to describe a heap
protected heap: T[];
constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
this.heap = []; }}Copy the code- Get left, right and parent node functions
// Get the position of the left child node
protected getLeftIndex(index: number) :number {
return 2 * index + 1;
}
// Get the position of the right child node
protected getRightIndex(index: number) :number {
return 2 * index + 2;
}
// Get the location of the parent node
protected getParentIndex(index: number) :number | undefined {
if (index === 0) {
return undefined;
}
return Math.floor((index - 1) / 2);
}
Copy the code- Implement the insert function
insert(value: T): boolean {
if(value ! =null) {
// Add elements to the leaves of the heap, i.e. the end of the array
this.heap.push(value);
// Move the node up to the appropriate position
this.siftUp(this.heap.length - 1);
return true;
}
return false;
}
// Implement the upshift function
protected siftUp(index: number) :void {
// Get the parent node location
let parent = <number>this.getParentIndex(index);
// The insertion position must be greater than 0 and its parent must be greater than itself to perform the operation in the loop
while (index > 0 && this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN) {
// Swap the position of the elements
this.swap(this.heap, parent, index);
// Change the position of the currently inserted value to its parent node, and retrieve the position of the parent node, i.e. repeat the process until the root node of the heap has also been swapped
index = parent;
parent = <number>this.getParentIndex(index); }}// Implement the swap array element position function
protected swap(array: T[], exchangeElement: number, exchangedElement: number) :void {
// Use a temporary variable to hold the exchange element
const temp = array[exchangeElement];
// Assign the swapped element to the swapped element
array[exchangeElement] = array[exchangedElement];
// Assign the temporary variable saved in the first step to the swapped element
array[exchangedElement] = temp;
}
Copy the code- Implement a minimum function that finds the heap
findMinimum(): T | undefined {
// Returns the smallest element of the array
return this.isEmpty() ? undefined : this.heap[0];
}
// Check whether the heap is empty
isEmpty(): boolean {
return this.size() === 0;
}
Copy the code- Implements the minimum function for exporting the heap
extract(): T | undefined {
if (this.isEmpty()) {
return undefined;
}
if (this.size() === 1) {
// Returns the first element of the array
return this.heap.shift();
}
const removedValue = this.heap.shift();
// Perform the move down operation
this.siftDown(0);
return removedValue;
}
// Move down
protected siftDown(index: number) :void {
// Save the position of the current inserted value
let element = index;
// Get the position of its left and right child nodes
const left = this.getLeftIndex(index);
const right = this.getRightIndex(index);
const size = this.size();
// The element is valid and the current element is greater than its left child node
if (left < size && this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN) {
element = left;
}
// The element is valid. The current element is greater than its right child node
if (right < size && this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN) {
element = right;
}
// Find the location of the smallest node and verify that its value is the same as element
if(index ! == element) {// If not, swap it with the smallest element
this.swap(this.heap, index, element);
// Execute recursively
this.siftDown(element); }}Copy the codeFull code address: heap.ts
Heap sort
One application of heap is heap sort, which is not explained here. For developers who do not know heap sort, please refer to my other article: Sorting algorithm: Understanding and implementation of heap sort
- Implement heapsort functions
heapSort(array: T[]): void {
/ / build the heap
this.buildHeap(array);
// Start at the end of the heap, swap the iterated elements with 0 better elements, and move down
for (let i = array.length - 1; i >= 0; i--) {
this.swap(array, i, 0);
this.heapify(array, i, 0); }}/ / build the heap
private buildHeap(array: T[]) {
// Get the position of the last node
const last = array.length - 1;
const lastParent = <number>this.getParentIndex(last);
// Start heapify from the parent of the last node
for (let i = lastParent; i >= 0; i--) {
this.heapify(array, array.length, i); }}// Switch nodes
private heapify(array: T[], size: number, index: number) {
// Recursive baseline conditions
if (index >= size) {
return false;
}
// Find the left and right subtrees of the current node
const left = this.getLeftIndex(index);
const right = this.getRightIndex(index);
// Save the location of the node to be operated on
let element = index;
// Update element's value if the left child of the node being operated on is larger than its parent
if (left < size && this.compareFn(array[left], array[element]) === Compare.BIGGER_THAN) {
element = left;
}
Update element's value if the right child of the node being operated on is larger than its parent
if (right < size && this.compareFn(array[right], array[element]) === Compare.BIGGER_THAN) {
element = right;
}
// The position of element is not equal to the current node to operate on, swap element positions, recursive execution
if(element ! == index) {this.swap(array, element, index);
this.heapify(array, size, element); }}Copy the codeWrite test code
Let’s test the above code to see if it works
import { MinHeap, MaxHeap } from "./lib/Heap.ts";
const minHeap = new MinHeap();
minHeap.insert(13);
minHeap.insert(10);
minHeap.insert(5);
minHeap.insert(7);
minHeap.insert(4);
minHeap.insert(17);
console.log("All elements of the heap (min)", minHeap.getIsArray());
console.log("Minimum heap (min)", minHeap.findMinimum());
console.log(minHeap.extract());
console.log(minHeap.getIsArray());
console.log("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");
const maxHeap = new MaxHeap();
maxHeap.insert(13);
maxHeap.insert(10);
maxHeap.insert(5);
maxHeap.insert(7);
maxHeap.insert(4);
maxHeap.insert(17);
console.log("All elements of the heap (Max)", maxHeap.getIsArray());
console.log(maxHeap.extract());
console.log("Maximum heap (Max)", maxHeap.findMinimum());
console.log("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");
const arrayTest = [12.15.17.18.4.5.1.7.19.20];
minHeap.heapSort(arrayTest);
console.log(arrayTest);
Copy the code
Write in the last
- If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
- This article was first published in nuggets. Reprint is prohibited without permission 💌