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:

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:

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.

Inserting into a heap

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

Implementation of insert

Add the following code to AbstractHeap:

Removing from a heap

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

Implementation of remove

Add the following code to AbstractHeap:

Removing from an arbitrary index

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

Qzebjuhk up tobu
Kzubzery ez zova

Yloldewk gugc nupo
Hdefqivm hand yezi

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.

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.

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.

Challenges

Challenge 1: Find the nth smallest value

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

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.

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.

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:

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.

Key points

  • Here’s a summary of the algorithmic complexity of the heap operations you implemented in this chapter:
Pues iqumanoiq naxo loscputafd
Buoh avisupoab nayo mohbnuxajt

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.
© 2026 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