Heap Data Structure Implementation — Swift 4

Motive

This post is aiming to help you understand the heap data structure and implement it in Swift. Prior knowledge of swift and heap are a must before we get into the implementation part.

What’s is Heap

Heap is a special type of complete binary tree where it’s parent is compared with its child nodes to give you the maximum or minimum value in the data structure.

There are two types in general.

1. Max Heap: In Max-Heap, the parent node will always be greater than it’s child nodes. All the other nodes can be in any order
2. Min Heap: In Min-Heap, the parent node will always be smaller than it’s child nodes. All the other nodes can be in any order
   .

Note: Heap data structure is useful when you only care about minimum or maximum value. All the other values will be unordered and unsorted.

Priority queues are the typical example where heap data structure can be used.

Implementation

For now, We will implement the minimum heap with all the functionalities. Implementation requires these following steps:

1. Adding a value to the heap

2. Removing the minimum element from the heap

3. Getting the minimum element from the heap

Let’s do this.

Creating Heap Class

Heaps can be represented by an array. A parent node can have a left and a right child. We can get the index of the right Child and left a child in the following way

Left Child Index = 2*parentIndex+ 1

Right Child Index = 2*parentIndex+2

In the same way,
ParentIndex = ( childIndex-1)/2

Implement Required Method in Heap Class

Add these methods in the heap class.

Now we will add methods for doing custom operations on Heap.

Add these methods

peek() returns the minimum element in the heap

poll() is the same like peek but it removes the minimum element as well

add() adds the element into the heap

removeMin() removes the minimum element in the heap

Now you must be wondering, what is heapifyDown() and heapifyUp()

Let’s implement them

HeapifyUp

It is the process which occurs after adding the element to the list. So if you want to add the element in the heap, you just add it to the last then you start comparing with the parent until the heap satisfies the condition

HeapifyDown

It is the process which occurs when you delete the minimum element in the list and heap has to rearrange itself to satisfy the conditions. For the parent node, it checks if the child node is smaller then the parent if yes, then swap the value. It continues until the heap satisfies its preconditions.

Let’s add the printMethod to print the heap

Let’s use these methods to play with the heap.

As you can see we added the elements in the heap in a random way. But when you print the heap at any time, it always prints the minimum value first.

See how it works with removal

That’s all the basic operations you can do with the heap. You can implement priority queues with the help of heaps. I would encourage you to implement it as it’s all fun.

Conclusion

So That’s it for this post. We have learned the basics of heap implementation in Swift. You can do much more with it, like priority queues.