Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

Second Edition · Android 11 · Kotlin 1.5 · IntelliJ IDEA Community Edition 2021.1

Before You Begin

Section 0: 7 chapters
Show chapters Hide chapters

Section I: Introduction to Data Structures & Algorithms

Section 1: 2 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 8 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 6 chapters
Show chapters Hide chapters

12. The Heap Data Structure
Written by Irina Galata

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Have you ever been to the arcade and played those crane machines that contain stuffed animals or cool prizes? These machines make it extremely difficult to win. But the fact that you set your eyes on the item you want is the very essence of the heap data structure!

Have you seen the movie Toy Story with the claw and the little green squeaky aliens? Just imagine that the claw machine operates on your heap data structure and will always pick the element with the highest priority.

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

What is a heap?

A heap is a complete binary tree data structure also known as a binary heap that you can construct using an array.

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

Heaps come in two flavors:

  1. Maxheap, in which elements with a higher value have a higher priority.
  2. Minheap, in which elements with a lower value have a higher priority.

Note: It’s important to say that the concept of heap is valid for every type of object that can be compared to others of the same type. In this chapter you’ll see mostly Ints but the same concepts are true for all Comparable types or, as you’ll see later, if a Comparator is provided .

A heap has an important characteristic that must always be satisfied. This is known as the heap invariant or heap property.

The heap property

Heap applications

Some useful applications of a heap include:

Common heap operations

Open the empty starter project for this chapter. Start by defining the following basic Collection type:

interface Collection<T: Any> {
  val count: Int

  val isEmpty: Boolean
    get() = count == 0

  fun insert(element: T)

  fun remove(): T?

  fun remove(index: Int): T?
}

interface Heap<T: Any> : Collection<T> {

  fun peek(): T?
}

Sorting and comparing

The heap properties imply there must be a way to compare each element and so a way to test if an element A is greater, smaller or equals than the element B. In Kotlin, as well as in Java, this can be achieved in 2 different ways:

abstract class AbstractHeap<T: Any>() : Heap<T> {

  abstract fun compare(a: T, b: T): Int
}

class ComparableHeapImpl<T : Comparable<T>>() : AbstractHeap<T>() {

  override fun compare(a: T, b: T): Int = a.compareTo(b)
}

class ComparatorHeapImpl<T: Any>(
    private val comparator: Comparator<T>
) : AbstractHeap<T>() {

  override fun compare(a: T, b: T): Int =
    comparator.compare(a, b)
}

How do you represent a heap?

Trees hold nodes that store references to their children. In the case of a binary tree, these are references to a left and a right child.

var elements: ArrayList<T> = ArrayList<T>()

override val count: Int
    get() = elements.size

override fun peek(): T? = elements.firstOrNull()

private fun leftChildIndex(index: Int) = (2 * index) + 1

private fun rightChildIndex(index: Int) = (2 * index) + 2

private fun parentIndex(index: Int) = (index - 1) / 2

Inserting into a heap

Suppose you insert a value of 7 to the heap below:

Implementation of insert

Add the following code to AbstractHeap:

override fun insert(element: T) {
  elements.add(element) // 1
  siftUp(count - 1) // 2
}

private fun siftUp(index: Int) {
  var child = index
  var parent = parentIndex(child)
  while (child > 0 && compare(elements[child], elements[parent]) > 0) {
    Collections.swap(elements, child, parent)
    child = parent
    parent = parentIndex(child)
  }
}

Removing from a heap

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

Implementation of remove

Add the following code to AbstractHeap:

override fun remove(): T? {
  if (isEmpty) return null // 1

  Collections.swap(elements, 0, count - 1) // 2
  val item = elements.removeAt(count - 1) // 3
  siftDown(0) // 4
  return item
}

private fun siftDown(index: Int) {
  var parent = index // 1
  while (true) { // 2
    val left = leftChildIndex(parent) //3
    val right = rightChildIndex(parent)
    var candidate = parent // 4
    if (left < count &&
      compare(elements[left], elements[candidate]) > 0) {
      candidate = left //5
    }
    if (right < count &&
      compare(elements[right], elements[candidate]) > 0) {
      candidate = right // 6
    }
    if (candidate == parent) {
      return // 7
    }
    Collections.swap(elements, parent, candidate) // 8
    parent = candidate
  }
}

Removing from an arbitrary index

Add the following method to AbstractHeap removing all the previous errors:

override fun remove(index: Int): T? {
  if (index >= count) return null // 1

  return if (index == count - 1) {
    elements.removeAt(count - 1) // 2
  } else {
    Collections.swap(elements, index, count - 1) // 3
    val item = elements.removeAt(count - 1) // 4
    siftDown(index) // 5
    siftUp(index)
    item
  }
}
Shifting up case
Zluvbafb ox fudi

Shifting down case
Crirfihw cebx vaja

Searching for an element in a heap

To find the index of the element that you want to delete, you must perform a search on the heap. Unfortunately, heaps are not designed for fast searches.

private fun index(element: T, i: Int): Int? {
  if (i >= count) {
    return null // 1
  }
  if (compare(element, elements[i]) > 0) {
    return null // 2
  }
  if (element == elements[i]) {
    return i // 3
  }

  val leftChildIndex = index(element, leftChildIndex(i))
  if (leftChildIndex != null) return leftChildIndex // 4
  val rightChildIndex = index(element, rightChildIndex(i))
  if (rightChildIndex != null) return rightChildIndex // 5
  return null // 6
}

Heapify an array

In the previous implementations of the Heap data structure, you have used an ArrayList. Other implementation could use an Array setting a max dimension for it. Making an existing array following the heap properties is an operation usually called heapify.

protected fun heapify(values: ArrayList<T>) {
  elements = values
  if (!elements.isEmpty()) {
    (count / 2 downTo 0).forEach {
      siftDown(it)
    }
  }
}


companion object {
  fun <T : Comparable<T>> create(
      elements: ArrayList<T>
  ): Heap<T> {
    val heap = ComparableHeapImpl<T>()
    heap.heapify(elements)
    return heap
  }
}

companion object {
  fun <T: Any> create(
      elements: ArrayList<T>,
      comparator: Comparator<T>
  ): Heap<T> {
    val heap = ComparatorHeapImpl(comparator)
    heap.heapify(elements)
    return heap
  }
}

Testing

You now have all the necessary tools to create and test a Heap. You can start using this code in order to create a max-heap of Comparable objects represented by Int values.

fun main() {
  val array = arrayListOf(1, 12, 3, 4, 1, 6, 8, 7) // 1
  val priorityQueue = ComparableHeapImpl.create(array) // 2
  while (!priorityQueue.isEmpty) { // 3
    println(priorityQueue.remove())
  }
}

12
8
7
6
4
3
1
1

fun main() {
  val array = arrayListOf(1, 12, 3, 4, 1, 6, 8, 7) // 1
  val inverseComparator = Comparator<Int> { o1, o2 ->  // 2
    override fun compare(o1: Int, o2: Int): Int = o2.compareTo(o1)
  }
  val minHeap = ComparatorHeapImpl.create(array, inverseComparator) // 3
  while (!minHeap.isEmpty) { // 4
    println(minHeap.remove())
  }
}

1
1
3
4
6
7
8
12

Challenges

Challenge 1: Find the nth smallest value

Write a function to find the nth smallest integer in an unsorted array. For example:

val integers = arrayListOf(3, 10, 18, 5, 21, 100)

Solution 1

There are many ways to solve for the nth smallest integer in an unsorted array. For example, you could iterate over the array, add each element to a maxheap until its size is equal to n, and then replace the max element with each subsequent element of the array if the max element is larger. This way peek() will always return nth smallest element of the array.

fun getNthSmallestElement(n: Int, elements: ArrayList<Int>): Int? {
  if (n <= 0 || elements.isEmpty()) return null

  val heap = ComparableHeapImpl.create(arrayListOf<Int>())

  elements.forEach { // 1
    val maxElement = heap.peek()
    if (heap.count < n) {
      heap.insert(it) // 2
    } else if (maxElement != null && maxElement > it) {
      heap.remove() // 3
      heap.insert(it) // 4
    }
  }

  return heap.peek() // 5
}

Challenge 2: The min heap visualization

Given the following array list, visually construct a minheap. Provide a step-by-step diagram of how the minheap is constructed.

arrayListOf(21, 10, 18, 5, 3, 100, 1)

Solution 2

Challenge 3: Heap merge

Write a method that combines two heaps.

Solution 3

Add this as an additional function for your AbstractHeap class after defining the same operation on the Heap interface:

override fun merge(heap: AbstractHeap<T>) {
  elements.addAll(heap.elements)
  buildHeap()
}

private fun buildHeap() {
  if (!elements.isEmpty()) {
    (count / 2 downTo 0).forEach {
      siftDown(it)
    }
  }
}

Challenge 4: Min heap check

Write a function to check if a given array is a minheap.

Solution 4

To check if the given array is a minheap, you only need to go through the parent nodes of the binary heap. To satisfy the minheap, every parent node must be less than or equal to its left and right child node.

override fun isMinHeap(): Boolean {
  if (isEmpty) return true // 1
  (count / 2 - 1 downTo 0).forEach {
    // 2
    val left = leftChildIndex(it) // 3
    val right = rightChildIndex(it)
    if (left < count &&
      compare(elements[left], elements[it]) < 0) { // 4
      return false
    }
    if (right < count
      && compare(elements[right], elements[it]) < 0) { // 5
      return false
    }
  }
  return true // 6
}

Key points

  • Here’s a summary of the algorithmic complexity of the heap operations you implemented in this chapter:
Heap operation time complexity
Dais upidayauc lema lilzpibadl

11. Binary Search
13. 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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now