1. What is binary heap
Binary heap is a very famous data structure in computer science, because it can find maximum and minimum values efficiently and quickly
Binary heap is a special binary tree, which has the following two characteristics.
- It is a complete binary tree, meaning that each layer of the tree has left and right child nodes (except for the leaf node in the last layer),
And as far as possible, the leaf nodes of the last layer are left child nodes, which is called structural characteristics.
- A binary heap is either the smallest heap or the largest heap. The minimum heap allows you to quickly export the minimum value of the tree, and the maximum heap allows you to quickly export the maximum value of the tree. All nodes are greater than or equal to (maximum heap) or less than or equal to (minimum heap) each of its children. This is called heap property
There are two ways to represent a binary tree. The first is to use a dynamic representation called a pointer (represented by a node). The second is to use an array that retrieves the values of the parent node and the left and right child nodes by index values. The following figure shows two different representations
2. Create a binary heap
To access a binary tree node that uses a normal array, we can manipulate index as follows. For a node at a given position index:
- The position of its left child node is 2 * index + 1 (if the position is available);
- The position of its right child node is 2 * index + 2 (if the position is available);
- Its parent position is index / 2 (if available)
class MinHeap {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
this.heap = [];
}
getLeftIndex(index) { / / the left node
return (2 * index) + 1;
}
getRightIndex(index) { / / right node
return (2 * index) + 2;
}
getParentIndex(index) { / / the parent node
if (index === 0) {
return undefined;
}
return Math.floor((index - 1) / 2);
}
size() {
return this.heap.length;
}
isEmpty() {
return this.size() <= 0;
}
clear() {
this.heap = [];
}
findMinimum() { // Returns the minimum (minimum heap) or maximum value
return this.isEmpty() ? undefined : this.heap[0];
}
insert(value) { // Insert a new value into the heap
if(value ! =null) {
const index = this.heap.length;
this.heap.push(value);
this.siftUp(index);
return true;
}
return false;
}
siftUp(index) { // Move up
let parent = this.getParentIndex(index);
while (
index > 0 &&
this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN
) {
swap(this.heap, parent, index);
index = parent;
parent = this.getParentIndex(index); }}siftDown(index) { // Move down
// Copy index into the element variable
let element = index;
// Get the values of the left and right child nodes
const left = this.getLeftIndex(index);
const right = this.getRightIndex(index);
const size = this.size();
// Swap elements with the smallest node (the smallest heap) and the largest child node (the largest heap)
if (
left < size &&
this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN
) {
If the element is smaller than the left child, we swap the element and its left child
element = left;
}
if (
right < size &&
this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN
) {
If the element is smaller than its right child, we swap the element and its right child
element = right;
}
if(index ! == element) {// Verify that it has the same value as element
// If not, swap it with the smallest element
swap(this.heap, index, element);
this.siftDown(element); }}extract() { // Remove the minimum (minimum heap) or maximum
if (this.isEmpty()) {
return undefined;
}
if (this.size() === 1) {
return this.heap.shift();
}
const removedValue = this.heap[0];
this.heap[0] = this.heap.pop();
this.siftDown(0);
return removedValue;
}
heapify(array) {
if (array) {
this.heap = array;
}
const maxIndex = Math.floor(this.size() / 2) - 1;
for (let i = 0; i <= maxIndex; i++) {
this.siftDown(i);
}
return this.heap;
}
getAsArray() {
return this.heap; }}export class MaxHeap extends MinHeap {
constructor(compareFn = defaultCompare) {
super(compareFn);
this.compareFn = compareFn;
this.compareFn = reverseCompare(compareFn); }}Copy the codeInsert:
Insert a value of 1 into the heap. The algorithm does a little bit of a shift up
Move down the operation
The algorithm of the MaxHeap class is exactly the same as that of the MinHeap class. The difference is that we want to replace all > (greater than) comparisons with < (less than) comparisons
export class MaxHeap extends MinHeap {
constructor(compareFn = defaultCompare) {
super(compareFn);
this.compareFn = reverseCompare(compareFn); / / {1}}}Copy the codeYou can extend the MinHeap class to inherit all of the code we created in this chapter and do reverse comparisons if necessary. To reverse the comparison, instead of comparing a with B, compare B with A
function reverseCompare(compareFn) {
return (a, b) = > compareFn(b, a);
}
Copy the codeJane version
class MinHeap {
constructor() {
this.heap = [];
}
// Switch nodes
swap(i1, i2) {
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
// Get the parent node
getParentIndex(i) {
// return Math.floor((i - 1) / 2);
return (i - 1) > >1; // base 2 operation, quotient
}
getLeftIndex(i) {
return i * 2 + 1;
}
getRightIndex(i) {
return i * 2 + 2;
}
/ / up
shiftUp(index) {
if (index == 0) { return; }
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] > this.heap[index]) { // The parent node is larger than the current node
this.swap(parentIndex, index);
this.shiftUp(parentIndex); }}// Move down
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if (this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if (this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex); }}// Inserts the value at the bottom of the heap, at the end of the array.
// Then _ up: the value is swapped with its parent until the parent is less than or equal to the inserted value
// The time of inserting elements into the heap of size k is O(logK)
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
// Delete the heap top
// Replace the top of the heap with the element at the end of the array (removing the top directly breaks the heap structure).
// Then move down: swap the new heap top with its children until the children are greater than or equal to the new heap top.
// The time complexity for removing the top of a heap of size K is O(logK).
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0);
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length; }}const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);
h.pop();
Copy the code3. Heap sort algorithm
We can use binary heap data structures to help us create a very famous sorting algorithm: the heapsort algorithm. It consists of the following three steps.
(1) Create a maximum heap of arrays to use as source data. (2) After the maximum heap is created, the maximum value is stored in the first location of the heap. We’re going to replace it with the last value of the heap, minus the size of the heap by one. (3) Finally, we move the root node of the heap down and repeat Step 2 until the heap size is 1
We use the maximum heap to get an array in ascending order (from smallest to largest). If we want the array to be sorted in descending order, we can use the minimum heap instead
Heapsort algorithm
function heapSort(array, compareFn = defaultCompare) {
let heapSize = array.length;
buildMaxHeap(array, compareFn); / / step 1
while (heapSize > 1) {
swap(array, 0, --heapSize); / / step 2
heapify(array, 0, heapSize, compareFn); / / step 3
}
return array;
}
Copy the codeBuild maximum heap
function buildMaxHeap(array, compareFn) {
for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
heapify(array, i, array.length, compareFn);
}
return array;
}
Copy the codeThe maximum heap function reorganizes the order of the array. Thanks to all the comparisons to be made, we only need to execute the Heapify (move down) function on the second half of the array (the first half will be sorted automatically, so there is no need to execute the function on the part that is already known to be sorted).
The Heapify function has the same code as the siftDown method we created. The difference is that we pass in as arguments the heap itself, the size of the heap, and the comparison function to use. This is because instead of using the heap data structure directly, we use its logic to develop the heapSort algorithm
4. Application of heap
The heap can find the maximum and minimum values efficiently and quickly, time complexity: O(1) ◆ Find the K largest (small) element
The KTH largest element
◆ Build a minimum heap and insert elements into the heap at once. ◆ Remove the heap top when the heap size exceeds K. ◆ After insertion, the top of the heap is the KTH largest element
5. Leetcode
1.The KTH largest element in the array
Difficulty: Medium
The KTH largest element in an array (the smallest heap)
2.The first K high frequency elements
Difficulty: Medium
Solution: the first K high frequency elements (minimum heap)
3.Merge K ascending linked lists
Difficulty: difficulty
Merge K ascending linked lists (minimum heap)