Home Android & Kotlin Books Data Structures & Algorithms in Kotlin

12
The Heap Data Structure Written by Irina Galata, Kelvin Lau and Vincent Ngo

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 raywenderlich.com Professional subscription.

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<Element> {
  val count: Int
    get

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

  fun insert(element: Element)

  fun remove(): Element?

  fun remove(index: Int): Element?
}

interface Heap<Element> : Collection<Element> {

  fun peek(): Element?
}

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<Element>() : Heap<Element> {

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

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

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

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

  override fun compare(a: Element, b: Element): 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<Element> = ArrayList<Element>()

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

override fun peek(): Element? = elements.first()

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: Element) {
  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(): Element? {
  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): Element? {
  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
Ggegfadf es ribo

Shifting down case
Gsamnozp yipg lubi

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: Element, i: Int): Int? {
  if (i >= count) {
    return null // 1
  }
  if (sort(element, elements[i])) {
    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<Element>) {
  elements = values
  if (!elements.isEmpty()) {
    (count / 2 downTo 0).forEach {
      siftDown(it)
    }
  }
}


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

companion object {
  fun <Element> create(
      elements: ArrayList<Element>,
      comparator: Comparator<Element>
  ): Heap<Element> {
    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 = object : Comparator<Int> { // 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 choose a sorting algorithm you learned in this chapter, sort the array, and grab the element at the nth index.

fun getNthSmallestElement(n: Element): Element? {
  var current = 1 // 1
  while (!isEmpty) { // 2
    val element = remove() // 3
    if (current == n) { // 4
      return element
    }
    current += 1 // 5
  }
  return null // 6
}

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(3, 10, 18, 5, 21, 100)

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<Element>) {
  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
Caec icigazaeb yewi kujxxodulr

13. Priority Queues 11. Binary Search

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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

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 raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99