Data Structures. Heap

29 ноября 2023 г.

This is a short expanded summary of the section about heaps in the book Computer Science Guide by William Springer.

Basic information

A heap is a nearly complete binary tree (a tree that is fully filled on all levels except possibly the last one, which is filled from left to right). The root key is either greater than or equal to all its children (in a max-heap) or smaller than or equal to all its children (in a min-heap). This property holds for every subtree.

After each operation, the heap reorders itself so that all levels of the tree (except possibly the last) remain filled.

A heap is partially ordered by keys — the element with the highest (or lowest) priority is always at the root.

Heaps are typically implemented using arrays. Just like in a stack, only one element can be removed at a time — but in a heap, it is not the last inserted element, but the largest (in a max-heap) or smallest (in a min-heap).

Example of a max-heap:

Sibling nodes (nodes that share the same parent) are not directly connected to each other. They have lower priority than their parent.

In a min-heap, the value of every node is greater than or equal to the value of its parent.

A heap supports the following operations:

finding the maximum value (find-max / peek),
inserting a new element (insert / push),
extracting the maximum value (extract-max / pop),
increasing a key (increase-key) — changing the value of a node and then moving it to its appropriate position in the heap.

In a max-heap, the value of every node is less than or equal to the value of its parent.

Unless otherwise specified, the term heap usually refers to a binary heap — a complete binary tree that satisfies the heap property.

For a binary heap, after building the heap from a list of elements in O(n) time, each of the operations above takes O(lg n) time.

Other types of heaps include leftist heaps, binomial heaps, and Fibonacci heaps.

Heaps are used when fast access to the largest (or smallest) element is required without sorting the entire collection. A common application is implementing priority queues, where the relative order of all elements is unimportant—the only thing that matters is which element has the highest priority and should be processed next. This element is always stored at the root of the heap.

Heap Implementation

The nodes are numbered starting from the root, then from left to right at each level.

The root is node 0.
Its left child is node 1.
Its right child is node 2.
The leftmost grandchild of the root is node 3, and so on.

In this example, nodes 5 through 9 are the roots of heaps of size 1. In general, for a heap of size n, every element at an index from Math.floor(n / 2) to n - 1 is the root of a heap of size 1 (a leaf node).

For any node k:

its parent is at index Math.floor((k - 1) / 2);
its children (if they exist) are at indices 2k + 1 and 2k + 2.

To efficiently determine the position of a parent or child node, multiplication and division by two can be performed using bit shifts. This allows the required node's index to be calculated efficiently when the heap is implemented as an array.

A heap is built recursively. Small heaps are created first and then combined into larger heaps.

The following example of heap construction is taken from this website:

In the example below, a min-heap is built, where the smallest element is always located at the root of the heap. To build a max-heap, we need to use the comparator function:

const comparator = (a, b) => b - a;

Let's create a Heap class and define its helper methods.

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4	constructor(comparator) {
5		this.arr = [];
6		this.comparator = comparator;
7	}
8
9	isCorrectOrder(first, second) {
10		return this.comparator(first, second) < 0;
11	}
12
13	getLeftChildIndex(parentIndex) {
14		return 2 * parentIndex + 1;
15	}
16
17	getRightChildIndex(parentIndex) {
18		return 2 * parentIndex + 2;
19	}
20
21	getParentIndex(childIndex) {
22		return Math.floor((childIndex - 1) / 2);
23	}
24
25	leftChild(parentIndex) {
26		return this.arr[this.getLeftChildIndex(parentIndex)];
27	}
28
29	rightChild(parentIndex) {
30		return this.arr[this.getRightChildIndex(parentIndex)];
31	}
32
33	parent(childIndex) {
34		return this.arr[this.getParentIndex(childIndex)];
35	}
36
37	hasParent(childIndex) {
38		return this.getParentIndex(childIndex) >= 0;
39	}
40
41	hasLeftChild(parentIndex) {
42		return this.getLeftChildIndex(parentIndex) < this.arr.length;
43	}
44
45	hasRightChild(parentIndex) {
46		return this.getRightChildIndex(parentIndex) < this.arr.length;
47	}
48
49	isEmpty() {
50		return !this.arr.length;
51	}
52}

Inserting an Element

The new element is placed in the first empty position of the array. If the new element is smaller than its parent (for a min-heap), it is moved upward recursively by swapping it with its parent until it becomes greater than its parent or reaches the root of the heap.

The maximum height of the tree is O(lg n), and each comparison/swap operation takes O(1) time. Therefore, the total time complexity of insertion is O(lg n).

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4    // ...
5	push(item) {
6		this.arr.push(item);
7		this.heapifyUp();
8		return this;
9	}
10
11	heapifyUp(startIndex) {
12		let currentIndex = startIndex || this.arr.length - 1;
13
14		// While the element has a parent and the element is smaller than its parent,
15        // swap the element with its parent.
16
17		while (
18			this.hasParent(currentIndex) &&
19			!this.isCorrectOrder(
20				this.parent(currentIndex),
21				this.arr[currentIndex]
22			)
23		) {
24			let parentIndex = this.getParentIndex(currentIndex);
25			this.swap(currentIndex, parentIndex);
26			currentIndex = parentIndex;
27		}
28	}
29
30	swap(indexOne, indexTwo) {
31		const tmp = this.arr[indexTwo];
32		this.arr[indexTwo] = this.arr[indexOne];
33		this.arr[indexOne] = tmp;
34	}
35}
36
37const heap = new Heap(comparator);
38
39heap.push(14);
40heap.push(18);
41heap.push(4);
42heap.push(29);
43heap.push(18);
44heap.push(44);
45heap.push(3);
46console.log(heap);
47//[3, 18,  4, 29, 18, 44, 14]

Removing the Root from a Heap

When the root of a heap is removed, an empty space remains. This space is filled with the last element of the heap (from the lowest level), while maintaining an almost complete binary tree structure.

Then, the new root is moved downward by swapping it with child nodes that have smaller values until the tree satisfies the heap property again.

JavaScript

1class Heap {
2    //...
3	pop() {
4		if (this.arr.length === 0) {
5			return null;
6		}
7
8		if (this.arr.length === 1) {
9			return this.arr.pop();
10		}
11
12		const item = this.arr[0];
13
14		this.arr[0] = this.arr.pop();
15		this.heapifyDown();
16
17		return item;
18	}
19
20	heapifyDown(customStartIndex = 0) {
21		let currentIndex = customStartIndex;
22		let nextIndex = null;
23
24		while (this.hasLeftChild(currentIndex)) {
25			if (
26				this.hasRightChild(currentIndex) &&
27				this.isCorrectOrder(
28					this.rightChild(currentIndex),
29					this.leftChild(currentIndex)
30				)
31			) {
32				nextIndex = this.getRightChildIndex(currentIndex);
33			} else {
34				nextIndex = this.getLeftChildIndex(currentIndex);
35			}
36
37			if (
38				this.isCorrectOrder(this.arr[currentIndex], this.arr[nextIndex])
39			) {
40				break;
41			}
42
43			this.swap(currentIndex, nextIndex);
44			currentIndex = nextIndex;
45		}
46	}
47}
48
49//[3, 18,  4, 29, 18, 44, 14]
50heapArr.pop(3);
51// [ 4, 18, 14, 29, 18, 44 ]

Converting an Array into a Heap

The given array is stored as the heap array, and the heapify method is called for each element to restore the heap property.yUp.

JavaScript

1class Heap {
2   //...
3	buildHeap(array) {
4		this.arr = array;
5		let i = array.length - 1;
6		while (i > 1) {
7			this.heapifyUp(i)
8			i--;
9		}
10	}
11}
12
13const heap = new Heap(comparator);
14const arr = [24, 19, 2, 13, 101, 8];
15
16heap.buildHeap(arr);
17// [ 2, 24, 13, 19, 101, 8 ]

Full code

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4	constructor(comparator) {
5		this.arr = [];
6		this.comparator = comparator;
7	}
8
9	isCorrectOrder(first, second) {
10		return this.comparator(first, second) < 0;
11	}
12
13	getLeftChildIndex(parentIndex) {
14		return 2 * parentIndex + 1;
15	}
16
17	getRightChildIndex(parentIndex) {
18		return 2 * parentIndex + 2;
19	}
20
21	getParentIndex(childIndex) {
22		return Math.floor((childIndex - 1) / 2);
23	}
24
25	leftChild(parentIndex) {
26		return this.arr[this.getLeftChildIndex(parentIndex)];
27	}
28
29	rightChild(parentIndex) {
30		return this.arr[this.getRightChildIndex(parentIndex)];
31	}
32
33	parent(childIndex) {
34		return this.arr[this.getParentIndex(childIndex)];
35	}
36
37	hasParent(childIndex) {
38		return this.getParentIndex(childIndex) >= 0;
39	}
40
41	hasLeftChild(parentIndex) {
42		return this.getLeftChildIndex(parentIndex) < this.arr.length;
43	}
44
45	hasRightChild(parentIndex) {
46		return this.getRightChildIndex(parentIndex) < this.arr.length;
47	}
48
49	isEmpty() {
50		return !this.arr.length;
51	}
52
53	buildHeap(array) {
54		this.arr = array;
55		let i = array.length - 1;
56		while (i > 1) {
57			this.heapifyUp(i)
58			i--;
59		}
60	}
61
62	push(item) {
63		this.arr.push(item);
64		this.heapifyUp();
65		return this;
66	}
67
68	heapifyUp(startIndex) {
69		let currentIndex = startIndex || this.arr.length - 1;
70
71		while (
72			this.hasParent(currentIndex) &&
73			!this.isCorrectOrder(
74				this.parent(currentIndex),
75				this.arr[currentIndex]
76			)
77		) {
78			let parentIndex = this.getParentIndex(currentIndex);
79			this.swap(currentIndex, parentIndex);
80			currentIndex = parentIndex;
81		}
82	}
83
84	swap(indexOne, indexTwo) {
85		const tmp = this.arr[indexTwo];
86		this.arr[indexTwo] = this.arr[indexOne];
87		this.arr[indexOne] = tmp;
88	}
89
90	pop() {
91		if (this.arr.length === 0) {
92			return null;
93		}
94
95		if (this.arr.length === 1) {
96			return this.arr.pop();
97		}
98
99		const item = this.arr[0];
100
101		this.arr[0] = this.arr.pop();
102		this.heapifyDown();
103
104		return item;
105	}
106
107	heapifyDown(customStartIndex = 0) {
108		let currentIndex = customStartIndex;
109		let nextIndex = null;
110
111		while (this.hasLeftChild(currentIndex)) {
112			if (
113				this.hasRightChild(currentIndex) &&
114				this.isCorrectOrder(
115					this.rightChild(currentIndex),
116					this.leftChild(currentIndex)
117				)
118			) {
119				nextIndex = this.getRightChildIndex(currentIndex);
120			} else {
121				nextIndex = this.getLeftChildIndex(currentIndex);
122			}
123
124			if (
125				this.isCorrectOrder(this.arr[currentIndex], this.arr[nextIndex])
126			) {
127				break;
128			}
129
130			this.swap(currentIndex, nextIndex);
131			currentIndex = nextIndex;
132		}
133	}
134}

Data Structures. Heap

29 ноября 2023 г.

This is a short expanded summary of the section about heaps in the book Computer Science Guide by William Springer.

Basic information

After each operation, the heap reorders itself so that all levels of the tree (except possibly the last) remain filled.

A heap is partially ordered by keys — the element with the highest (or lowest) priority is always at the root.

Example of a max-heap:

Sibling nodes (nodes that share the same parent) are not directly connected to each other. They have lower priority than their parent.

In a min-heap, the value of every node is greater than or equal to the value of its parent.

A heap supports the following operations:

finding the maximum value (find-max / peek),
inserting a new element (insert / push),
extracting the maximum value (extract-max / pop),
increasing a key (increase-key) — changing the value of a node and then moving it to its appropriate position in the heap.

In a max-heap, the value of every node is less than or equal to the value of its parent.

Unless otherwise specified, the term heap usually refers to a binary heap — a complete binary tree that satisfies the heap property.

For a binary heap, after building the heap from a list of elements in O(n) time, each of the operations above takes O(lg n) time.

Other types of heaps include leftist heaps, binomial heaps, and Fibonacci heaps.

Heap Implementation

The nodes are numbered starting from the root, then from left to right at each level.

The root is node 0.
Its left child is node 1.
Its right child is node 2.
The leftmost grandchild of the root is node 3, and so on.

For any node k:

its parent is at index Math.floor((k - 1) / 2);
its children (if they exist) are at indices 2k + 1 and 2k + 2.

A heap is built recursively. Small heaps are created first and then combined into larger heaps.

The following example of heap construction is taken from this website:

In the example below, a min-heap is built, where the smallest element is always located at the root of the heap. To build a max-heap, we need to use the comparator function:

const comparator = (a, b) => b - a;

Let's create a Heap class and define its helper methods.

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4	constructor(comparator) {
5		this.arr = [];
6		this.comparator = comparator;
7	}
8
9	isCorrectOrder(first, second) {
10		return this.comparator(first, second) < 0;
11	}
12
13	getLeftChildIndex(parentIndex) {
14		return 2 * parentIndex + 1;
15	}
16
17	getRightChildIndex(parentIndex) {
18		return 2 * parentIndex + 2;
19	}
20
21	getParentIndex(childIndex) {
22		return Math.floor((childIndex - 1) / 2);
23	}
24
25	leftChild(parentIndex) {
26		return this.arr[this.getLeftChildIndex(parentIndex)];
27	}
28
29	rightChild(parentIndex) {
30		return this.arr[this.getRightChildIndex(parentIndex)];
31	}
32
33	parent(childIndex) {
34		return this.arr[this.getParentIndex(childIndex)];
35	}
36
37	hasParent(childIndex) {
38		return this.getParentIndex(childIndex) >= 0;
39	}
40
41	hasLeftChild(parentIndex) {
42		return this.getLeftChildIndex(parentIndex) < this.arr.length;
43	}
44
45	hasRightChild(parentIndex) {
46		return this.getRightChildIndex(parentIndex) < this.arr.length;
47	}
48
49	isEmpty() {
50		return !this.arr.length;
51	}
52}

Inserting an Element

The maximum height of the tree is O(lg n), and each comparison/swap operation takes O(1) time. Therefore, the total time complexity of insertion is O(lg n).

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4    // ...
5	push(item) {
6		this.arr.push(item);
7		this.heapifyUp();
8		return this;
9	}
10
11	heapifyUp(startIndex) {
12		let currentIndex = startIndex || this.arr.length - 1;
13
14		// While the element has a parent and the element is smaller than its parent,
15        // swap the element with its parent.
16
17		while (
18			this.hasParent(currentIndex) &&
19			!this.isCorrectOrder(
20				this.parent(currentIndex),
21				this.arr[currentIndex]
22			)
23		) {
24			let parentIndex = this.getParentIndex(currentIndex);
25			this.swap(currentIndex, parentIndex);
26			currentIndex = parentIndex;
27		}
28	}
29
30	swap(indexOne, indexTwo) {
31		const tmp = this.arr[indexTwo];
32		this.arr[indexTwo] = this.arr[indexOne];
33		this.arr[indexOne] = tmp;
34	}
35}
36
37const heap = new Heap(comparator);
38
39heap.push(14);
40heap.push(18);
41heap.push(4);
42heap.push(29);
43heap.push(18);
44heap.push(44);
45heap.push(3);
46console.log(heap);
47//[3, 18,  4, 29, 18, 44, 14]

Removing the Root from a Heap

When the root of a heap is removed, an empty space remains. This space is filled with the last element of the heap (from the lowest level), while maintaining an almost complete binary tree structure.

Then, the new root is moved downward by swapping it with child nodes that have smaller values until the tree satisfies the heap property again.

JavaScript

1class Heap {
2    //...
3	pop() {
4		if (this.arr.length === 0) {
5			return null;
6		}
7
8		if (this.arr.length === 1) {
9			return this.arr.pop();
10		}
11
12		const item = this.arr[0];
13
14		this.arr[0] = this.arr.pop();
15		this.heapifyDown();
16
17		return item;
18	}
19
20	heapifyDown(customStartIndex = 0) {
21		let currentIndex = customStartIndex;
22		let nextIndex = null;
23
24		while (this.hasLeftChild(currentIndex)) {
25			if (
26				this.hasRightChild(currentIndex) &&
27				this.isCorrectOrder(
28					this.rightChild(currentIndex),
29					this.leftChild(currentIndex)
30				)
31			) {
32				nextIndex = this.getRightChildIndex(currentIndex);
33			} else {
34				nextIndex = this.getLeftChildIndex(currentIndex);
35			}
36
37			if (
38				this.isCorrectOrder(this.arr[currentIndex], this.arr[nextIndex])
39			) {
40				break;
41			}
42
43			this.swap(currentIndex, nextIndex);
44			currentIndex = nextIndex;
45		}
46	}
47}
48
49//[3, 18,  4, 29, 18, 44, 14]
50heapArr.pop(3);
51// [ 4, 18, 14, 29, 18, 44 ]

Converting an Array into a Heap

The given array is stored as the heap array, and the heapify method is called for each element to restore the heap property.yUp.

JavaScript

1class Heap {
2   //...
3	buildHeap(array) {
4		this.arr = array;
5		let i = array.length - 1;
6		while (i > 1) {
7			this.heapifyUp(i)
8			i--;
9		}
10	}
11}
12
13const heap = new Heap(comparator);
14const arr = [24, 19, 2, 13, 101, 8];
15
16heap.buildHeap(arr);
17// [ 2, 24, 13, 19, 101, 8 ]

Full code

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4	constructor(comparator) {
5		this.arr = [];
6		this.comparator = comparator;
7	}
8
9	isCorrectOrder(first, second) {
10		return this.comparator(first, second) < 0;
11	}
12
13	getLeftChildIndex(parentIndex) {
14		return 2 * parentIndex + 1;
15	}
16
17	getRightChildIndex(parentIndex) {
18		return 2 * parentIndex + 2;
19	}
20
21	getParentIndex(childIndex) {
22		return Math.floor((childIndex - 1) / 2);
23	}
24
25	leftChild(parentIndex) {
26		return this.arr[this.getLeftChildIndex(parentIndex)];
27	}
28
29	rightChild(parentIndex) {
30		return this.arr[this.getRightChildIndex(parentIndex)];
31	}
32
33	parent(childIndex) {
34		return this.arr[this.getParentIndex(childIndex)];
35	}
36
37	hasParent(childIndex) {
38		return this.getParentIndex(childIndex) >= 0;
39	}
40
41	hasLeftChild(parentIndex) {
42		return this.getLeftChildIndex(parentIndex) < this.arr.length;
43	}
44
45	hasRightChild(parentIndex) {
46		return this.getRightChildIndex(parentIndex) < this.arr.length;
47	}
48
49	isEmpty() {
50		return !this.arr.length;
51	}
52
53	buildHeap(array) {
54		this.arr = array;
55		let i = array.length - 1;
56		while (i > 1) {
57			this.heapifyUp(i)
58			i--;
59		}
60	}
61
62	push(item) {
63		this.arr.push(item);
64		this.heapifyUp();
65		return this;
66	}
67
68	heapifyUp(startIndex) {
69		let currentIndex = startIndex || this.arr.length - 1;
70
71		while (
72			this.hasParent(currentIndex) &&
73			!this.isCorrectOrder(
74				this.parent(currentIndex),
75				this.arr[currentIndex]
76			)
77		) {
78			let parentIndex = this.getParentIndex(currentIndex);
79			this.swap(currentIndex, parentIndex);
80			currentIndex = parentIndex;
81		}
82	}
83
84	swap(indexOne, indexTwo) {
85		const tmp = this.arr[indexTwo];
86		this.arr[indexTwo] = this.arr[indexOne];
87		this.arr[indexOne] = tmp;
88	}
89
90	pop() {
91		if (this.arr.length === 0) {
92			return null;
93		}
94
95		if (this.arr.length === 1) {
96			return this.arr.pop();
97		}
98
99		const item = this.arr[0];
100
101		this.arr[0] = this.arr.pop();
102		this.heapifyDown();
103
104		return item;
105	}
106
107	heapifyDown(customStartIndex = 0) {
108		let currentIndex = customStartIndex;
109		let nextIndex = null;
110
111		while (this.hasLeftChild(currentIndex)) {
112			if (
113				this.hasRightChild(currentIndex) &&
114				this.isCorrectOrder(
115					this.rightChild(currentIndex),
116					this.leftChild(currentIndex)
117				)
118			) {
119				nextIndex = this.getRightChildIndex(currentIndex);
120			} else {
121				nextIndex = this.getLeftChildIndex(currentIndex);
122			}
123
124			if (
125				this.isCorrectOrder(this.arr[currentIndex], this.arr[nextIndex])
126			) {
127				break;
128			}
129
130			this.swap(currentIndex, nextIndex);
131			currentIndex = nextIndex;
132		}
133	}
134}