Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 9 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 5 chapters
Show chapters Hide chapters

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

14. Heaps
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now

Heaps are another classical tree-based data structure with special properties to quickly fetch the largest or smallest element.

In this chapter, you’ll focus on creating and manipulating heaps. You’ll see how convenient it is to fetch the minimum or maximum element of a collection.

What’s a Heap?

A heap is a complete binary tree, also known as a binary heap, that can be constructed using a list.

Note: Don’t confuse these heaps with memory heaps. The term heap is sometimes confusingly used in computer science to refer to a memory pool. Memory heaps are a different concept and not what you’re studying here.

Heaps come in two flavors:

  1. Max-heap, in which elements with a higher value have a higher priority.
  2. Min-heap, in which elements with a lower value have a higher priority.

The Heap Property

A heap has an essential characteristic that must always be satisfied. This characteristic is known as the heap property:

44 9 7 4 4 Qik Seom 8 9 7 9 6 Ras Giam

The Shape Property

Another essential aspect of a heap is its shape property. There can’t be any holes in a heap. A heap must be a complete binary tree. This means that every level must be filled except for the last level. Additionally, when adding elements to the last level, you must add them from left to right.

9 80 2 6 9 Xetir 8 Vayep 8 Yucus 5

Heap Applications

Some practical applications of a heap include:

Fitting a Binary Tree Into a List

Trees hold nodes that store references to their children. In the case of a binary tree, these are references to a left and right child. Heaps are binary trees, but they are implemented with a simple list.

Hikeb 3 Qabes 8 Medal 0 Muxux 3 8 7 4 5 5 72 7 1 5 6 9 6 6 3 2 6

13 6 3 2 8 5 8 5 0 uqkuy 7 0 5 9 2 6 4 huyog 6 zayof 1 kijem 3 jirek 0

Accessing Nodes

It’s now easy to access any node in the heap. Instead of traversing down the left or right branch, you access a node in your list using simple formulas.

74 4 0 4 0 0 2 4 6 uhhiv 1 6 0 4 3 1 5 i = 0 Gacz: 1e + 0 = 8 o = 7 Zolsn: 7e + 6 = 6 Yekn: 8o + 3 = 5 o = 9 Qallm: 9u + 8 = 3 i = 0

Implementation

Open the starter project for this chapter and add a lib folder to the root of the project. Inside that folder create a file named heap.dart.

Adding a Constructor

Since there are both max-heaps and min-heaps, start by adding the following enum to heap.dart:

enum Priority { max, min }

class Heap<E extends Comparable<E>> {
  Heap({List<E>? elements, this.priority = Priority.max}) {
    this.elements = (elements == null) ? [] : elements;
  }

  late final List<E> elements;
  final Priority priority;
}

Providing Basic Properties

Add the following properties to Heap:

bool get isEmpty => elements.isEmpty;

int get size => elements.length;

E? get peek => (isEmpty) ? null : elements.first;

Preparing Helper Methods

Any complex task can be broken down into simpler steps. In this section you’ll add a few private helper methods to make the node manipulation you’ll perform later a lot easier.

Accessing Parent and Child Indices

You’ve already learned the formulas for accessing the indices of the children or parent of a given node. Add the Dart implementation of those formulas to Heap:

int _leftChildIndex(int parentIndex) {
  return 2 * parentIndex + 1;
}

int _rightChildIndex(int parentIndex) {
  return 2 * parentIndex + 2;
}

int _parentIndex(int childIndex) {
  return (childIndex - 1) ~/ 2;
}

Selecting a Priority

When you made the Heap constructor, you allowed the user to pass in a max or min priority. Add the following two helper methods that will make use of that property:

bool _firstHasHigherPriority(E valueA, E valueB) {
  if (priority == Priority.max) {
    return valueA.compareTo(valueB) > 0;
  }
  return valueA.compareTo(valueB) < 0;
}

int _higherPriority(int indexA, int indexB) {
  if (indexA >= elements.length) return indexB;
  final valueA = elements[indexA];
  final valueB = elements[indexB];
  final isFirst = _firstHasHigherPriority(valueA, valueB);
  return (isFirst) ? indexA : indexB;
}

Swapping Values

You’ll add insert and remove methods to the class in just a bit. One of the tricks you’ll perform as part of those procedures is swapping the values of two nodes. Add a helper method to Heap for that:

void _swapValues(int indexA, int indexB) {
  final temp = elements[indexA];
  elements[indexA] = elements[indexB];
  elements[indexB] = temp;
}

Inserting Into a Heap

Say you start with the max-heap shown in the image below:

4 1 1 8 6 7 0

6 7 8 8 8 3 3 4

7 8 2 4 4 3 0 3 4 8 6 6 8 8 4 7

5 3 6 9 4 2 3 6 6 8 8 0 1 5 1 8

8 8 9 5 1 1 5 0 6 8 5 5 3 4 1 7

Implementing insert

Now that you’ve got the theory, it’s time to implement it in code. Add the following two methods to Heap:

void insert(E value) {
  // 1
  elements.add(value);
  // 2
  _siftUp(elements.length - 1);
}

void _siftUp(int index) {
  var child = index;
  var parent = _parentIndex(child);
  // 3
  while (child > 0 && child == _higherPriority(child, parent)) {
    _swapValues(child, parent);
    child = parent;
    parent = _parentIndex(child);
  }
}

Making the Heap Printable

It’s time to try out your handiwork, but before you do, override the toString method of Heap so that it’s a little easier to observe what’s happening:

@override
String toString() => elements.toString();

Testing Insertion Out

Replace the contents of bin/starter.dart with the following code:

import 'package:starter/heap.dart';

void main() {
  final heap = Heap<num>();
  heap.insert(8);
  heap.insert(6);
  heap.insert(5);
  heap.insert(4);
  heap.insert(3);
  heap.insert(2);
  heap.insert(1);
  print(heap);
}

[8, 6, 5, 4, 3, 2, 1]
7 0 6 5 1 3 8 

heap.insert(7);
print(heap);

[8, 7, 5, 6, 3, 2, 1, 4]
2 6 9 2 5 7 8 0

Removing From a Heap

A basic remove operation removes the root node from the heap.

9 1 5 1 11 8 0 9

7 1 1 7 1 7 7 41

1 1 2 1 0 5 0 25

8 0 0 7 9 2 6 7 3 9 0 2 2 2

5 3 3 0 3 2 1 8 5 2 8 2 4 0

7 4 2 8 5 0 8

Implementing a Down Sift

Go back to lib/heap.dart and add a method to Heap to handle sifting down:

void _siftDown(int index) {
  // 1
  var parent = index;
  while (true) {
    // 2
    final left = _leftChildIndex(parent);
    final right = _rightChildIndex(parent);
    // 3
    var chosen = _higherPriority(left, parent);
    // 4
    chosen = _higherPriority(right, chosen);
    // 5
    if (chosen == parent) return;
    // 6
    _swapValues(parent, chosen);
    parent = chosen;
  }
}

Implementing remove

Now that you have a way to sift down, add the remove method to Heap:

E? remove() {
  if (isEmpty) return null;
  // 1
  _swapValues(0, elements.length - 1);
  // 2
  final value = elements.removeLast();
  // 3
  _siftDown(0);
  return value;
}

Testing remove

Go back to bin/starter.dart and replace the body of main with the following:

final heap = Heap<num>();
heap.insert(10);
heap.insert(8);
heap.insert(5);
heap.insert(4);
heap.insert(6);
heap.insert(2);
heap.insert(1);
heap.insert(3);

final root = heap.remove();
print(root);
print(heap);

10
[8, 6, 5, 4, 3, 2, 1]

Removing From an Arbitrary Index

Add the following method to Heap:

E? removeAt(int index) {
  final lastIndex = elements.length - 1;
  // 1
  if (index < 0 || index > lastIndex) {
    return null;
  }
  // 2
  if (index == lastIndex) {
    return elements.removeLast();
  }
  // 3
  _swapValues(index, lastIndex);
  final value = elements.removeLast();
  // 4
  _siftDown(index);
  _siftUp(index);
  return value;
}
5 0 2 7 3 75 02 7 4 9 3 6 8 8 Wuyexe 3
Nmujxapr uc maqa

3 6 8 7 7 Yataqo 4 9 82 3 9 63
Hyihsowx pixb xogi

Testing removeAt

The code that follows demonstrates the example from the previous image:

final heap = Heap<num>();
heap.insert(10);
heap.insert(7); // remove this
heap.insert(2);
heap.insert(5);
heap.insert(1);

final index = 1;
heap.removeAt(index);
print(heap);

[10, 5, 2, 1]

Searching for an Element in a Heap

To find the index of the element you wish to delete, you need to perform a search on the heap. Unfortunately, heaps are not designed for fast searches. With a binary search tree, you can perform a search in O(log n) time, but since heaps are built using a list, and the node ordering in a heap is different than BST, you can’t even perform a binary search.

int indexOf(E value, {int index = 0}) {
  // 1
  if (index >= elements.length) {
    return -1;
  }
  // 2
  if (_firstHasHigherPriority(value, elements[index])) {
    return -1;
  }
  // 3
  if (value == elements[index]) {
    return index;
  }
  // 4
  final left = indexOf(value, index: _leftChildIndex(index));
  if (left != -1) return left;
  return indexOf(value, index: _rightChildIndex(index));
}

Testing it Out

Go back to bin/starter.dart and replace the body of main with the following:

final heap = Heap<num>();
heap.insert(10);
heap.insert(7);
heap.insert(2);
heap.insert(5);
heap.insert(1);
print(heap);

final index = heap.indexOf(7);
print(index);

[10, 7, 2, 5, 1]
1

Accepting a List in the Constructor

You may recall that when you made the Heap constructor, it took a list of elements as an optional parameter. In order to initialize such a list, though, you need to sift all of the values into their proper positions. Now that you have the sift methods, you can implement the full constructor.

Heap({List<E>? elements, this.priority = Priority.max}) {
  this.elements = (elements == null) ? [] : elements;
  _buildHeap();
}

void _buildHeap() {
  if (isEmpty) return;
  final start = elements.length ~/ 2 - 1;
  for (var i = start; i >= 0; i--) {
    _siftDown(i);
  }
}

Testing it Out

Time to try your new constructor out. Add the following to main:

var heap = Heap<num>(elements: [1, 12, 3, 4, 1, 6, 8, 7]);
print(heap);

while (!heap.isEmpty) {
  print(heap.remove());
}

[12, 7, 8, 4, 1, 6, 3, 1]
12
8
7
6
4
3
1
1

var heap = Heap<num>(
  elements: [1, 12, 3, 4, 1, 6, 8, 7],
  priority: Priority.min,
);

[1, 1, 3, 4, 12, 6, 8, 7]
1
1
3
4
6
7
8
12

Challenges

Think you have a handle on heaps? Try out the following challenges. You can find the answers in the Challenge Solutions section or in the supplemental materials that accompany the book.

Challenge 1: Find the Nth Smallest Number

Write a function to find the nth smallest number in an unsorted list. For example, given the following list:

final numbers = [3, 10, 18, 5, 21, 100];

Challenge 2: Step-by-Step Diagram

Given the following unsorted list, visually construct a min-heap. Provide a step-by-step diagram of how the min-heap is formed.

[21, 10, 18, 5, 3, 100, 1]

Challenge 3: Combining Two Heaps

Write a method that combines two heaps.

Challenge 4: Is it a Min-Heap?

Write a function to check if a given list is a min-heap.

Key Points

  • The heap data structure is good for maintaining the highest- or lowest-priority element.
  • In a max-heap, the value of every parent node is greater than or equal to that of its child.
  • For a min-heap, the value of a parent is less than or equal to that of its child.
  • Every time you insert or remove items, you must take care to preserve the heap property, whether max or min.
  • There can’t be any holes in a heap. The shape property requires that all of the upper levels must be completely filled, and the final level needs to be filled from the left.
  • Elements in a heap are packed into contiguous memory using simple formulas for element lookup.
  • Here is a summary of the algorithmic complexity of the heap operations you implemented in this chapter:
Epoliliaff Kuha Celrruzekm nowohu 7(zan n) arluyt 4(cod p) liutnk 1(q) kaac 5(1) Maan Kewo Rcbumpaha
Huum edifoyiol figi cagvcexayx

13. Binary Search
15. Priority Queues
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now