iOS, Heap Data Structure

✍️ Note

Some codes and contents are sourced from Udemy. This post is for personal notes where I summarize the original contents to grasp the key concepts (🎨 some images I draw it)

Priority Queue

When a certain element in a collection has the highest weightage or priority – A common use case is to process that First

The data structure you use to store elements where the highest priority has to be processed first can be called a priority queue

At every step we access the element with the highest priority

The data structure needs to understand the priorities of the elements it holds

Common Operations

Insert elements (along with priority information)

Access the highest priority element

Remove the highest priority element

Use cases

Event simulation, Thread scheduling

Implementation

Case 1. Use an Array or List

Unordered

Insertion

Can be anywhere in the list or array – O(1)

Access

Accessing the highest priority element requires going through all elements in the List – O(N)

Remove

Removing the highest priority element requires going through all elements in the list – O(N)

Ordered

Insertion

Requires finding the right position for the element based on priority – O(N)

Access

Accessing the highest priority element is then easy – O(1)

Remove

Removing the highest priority element is straightforward – O(1)

Case 2. Balanced Binary Search Tree – All operations are O(LogN)

Insertion

Worst Case – O(LogN)

Access

Accessing the highest priority element is again O(LogN)

Remove

O(LogN)

Case 3. Binary Heap is the best for implementing Priority Queue

Insertion – O(LogN)

Access – O(1)

Remove – O(LogN)

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8473688#overview

Binary Heap

A heap is just a tree with a special properties or constraints on the values of its nodes

2 types

Minimum Heap

Root is the smallest value

Every node value should be <= value of it’s child

Maximum Heap

Root is the maximum value

Every node value should be >= value of it’s child

Constraints

Shape Property: If H is the Height of the Tree

THe leaf nodes should be only be at level H or H-1

Heap should from a complete binary Tree

All levels except the last should be filled

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8473690#content

Min-heap and max-heap diagrams showing their parent priority rules

Shape Property, Height

Complete min-heap shape with leaf nodes at height H or H minus 1

All nodes at Level H-1 nodes (9, 12, 11, 7) have to be filled before moving on to level H

Implementation

Logical structure of a binary heap is a Tree

Each node would have a pointer to the left and right child

Traverse

Traverse downwards from the root towards the leaf nodes

Traverse upward from the leaf nodes towards the root

Operations

Get left child

Get right child

Get parent

Heaps can be represented much more efficiently by using an array and having an implicit relationship to determine the parent, left and right child of a node

Every level of the binary tree in a heap is filled except perhaps the last

This means contiguous slots in an array can be used to represent binary tree levels
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8473692#content

Min-heap array representation with parent and child index formulas

Heapify

While inserting or removing an element into the heap How do we know which is the right position for the element to occupy?

HEAPIFY

We place a single element in the wrong position

Then we try and find the right position for the element

Operations

Sift Down

An element is in the wrong position with respect to other elements below it in the heap

It has to be moved downwards in the heap towards the leaf nodes to find it’s right position

Sift Up

An element is in the wrong position with respect to other elements above it in the heap

It has to be moved upwards in the heap towards the root node to find it’s right position

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8473704#content

HEAPIFY – Sift Down

Min-heap sift-down sequence moving value 13 through swaps with 6 and 7

			
protocol Heap {
    associatedtype Item: Comparable
    var array: [Item?] { get set }
    var count: Int { get set }
    
    init(_ input: [Item])
    
    func leftChildIndex(index: Int) -> Int?
    func rightChildIndex(index: Int) -> Int?
    func parentIndex(index: Int) -> Int?
    func siftDown(index: Int)
}
extension Heap {
    func leftChildIndex(index: Int) -> Int? {
        let leftIndex = 2 * index + 1
        if leftIndex >= count {
            return nil
        }
        return leftIndex
    }
    
    func rightChildIndex(index: Int) -> Int? {
        let rightIndex = 2 * index + 2
        if rightIndex >= count {
            return nil
        }
        return rightIndex
    }
    
    func parentIndex(index: Int) -> Int? {
        if index < 0 || index > count {
            return nil
        }
        return (index - 1) / 2
    }
    
    //MARK: Helper functions
    var isFull: Bool {
        count == array.count
    }
}
class MinHeap<T: Comparable>: Heap {
    var array: [T?]
    var count: Int
    
    required init(_ input: [T]) {
        self.array = input
        self.count = input.count
    }
    
    //Recursive call
    func siftDown(index: Int) {
        let leftChildIndex = leftChildIndex(index: index)
        let rightChildIndex = rightChildIndex(index: index)
        
        //smaller value in chids
        var swapCandidateIndex: Int?
        if leftChildIndex != nil, rightChildIndex != nil {
            if array[leftChildIndex!]! < array[rightChildIndex!]! {
                swapCandidateIndex = leftChildIndex
            }
            else {
                swapCandidateIndex = rightChildIndex
            }
        }
        else if leftChildIndex != nil {
            swapCandidateIndex = leftChildIndex
        }
        else if rightChildIndex != nil {
            swapCandidateIndex = rightChildIndex
        }
        
        //Base case
        guard let swapCandidateIndex, let swapCandidateValue = array[swapCandidateIndex], let currentIndexValue = array[index] else {
            return
        }
        
        if currentIndexValue > swapCandidateValue {
            let value = array[swapCandidateIndex]
            //Sift down large value to the next level
            array[swapCandidateIndex] = currentIndexValue
            array[index] = swapCandidateValue
            
            //Recursive Call
            siftDown(index: swapCandidateIndex)
        }
    }
}
let minHeap = MinHeap([13, 8, 6, 9, 12, 11, 7, 15, 10])
minHeap.siftDown(index: 0)
print(minHeap.array)

		

Swift siftDown implementation and the corrected min-heap array

HEAPIFY – Sift Up

Min-heap sift-up sequence comparing a node with each parent

Sift Up is much simpler than Sift Down

			
func siftUp(index: Int) {
        guard let parentIndex = parentIndex(index: index), let currentValue = array[index] else {
            return
        }
        if array[parentIndex]! > currentValue {
            let parentValue = array[parentIndex]!
            array[parentIndex] = currentValue
            array[index] = parentValue
            siftUp(index: parentIndex)
        }
    }

		

Swift siftUp implementation with the resulting min-heap array

Insert

Insert an element as a Leaf Node in the Heap

In an array implementation that would be at the very end – The newly inserted element would be the last element in the array

The element might be in the wrong position with respect to all nodes above it

It has to be moved Upwards in the heap towards the root node to find it’s right position

SIFT UP
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8473710?start=30#content

			
func insert(value: Item) {
    array.append(value)
    count = array.count
    let insertedIndex = array.count - 1
    siftUp(index: insertedIndex)
}

		

Swift min-heap insert function adding value 3 and printing the array

Remove

Remove the highest priority element in the heap I.E The minimum element

In an array implementation that would be the element at index 0

Copy over the last element in the array to index 0

The element might be in the wrong position with respect to all nodes below it

It has to be moved downwards in the heap towards the leaf nodes to find it’s right position

SIFT DOWN
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8473710?start=30#content

Min-heap removal sequence moving the last value to the root and sifting down

Min-heap swaps that restore order after removing the root

			
func removeHighestPriority() -> T? {
    let root = array[0]
    let lastElement = array[array.count - 1]
    array.removeFirst()
    array.insert(lastElement, at: 0)
    count = array.count
    siftDown(index: 0)
    return root
}

		

Swift removeHighestPriority function returning 2 and reheapifying the min-heap

I rewrote removeHighestPriority. Because removeFirst() It took O(N).

			
func removeHighestPriority() -> T? {
    //swapAt is O(1), Now root is last item
    array.swapAt(0, array.count - 1)
    //removeLast() is O(1)
    array.removeLast()
    count = array.count
    siftDown(index: 0)
    return root
}

		

Binary Heap Complexity

Insertion – Inserting a new element O(logN)

Access – Accessing the Highest priority element O(1)

Remove – Removing the highest priority element is O(logN)
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8473710?start=30#content

Heap Sort

Uses a heap to help sort elements in ascending or descending order

Step 1. Heapify: First converts the unsorted list or array into a heap – This can be done in place (No needs additional spaces)

Take a portion of the array – Make all elements in that portion satisfy the heap property

Keep adding additional elements into the heap portion ensuring that these additional elements also satisfy the heap property

The heap will grow to encompass all elements in the array

Step 2. Sort: Use the heap to access the maximum element and put it in the right position in the array (Heap to sorted array)

A heap offers O(1) access to the largest or the smallest element

Remove the largest element from the heap and position it at the end of the sorted array

The sorted array will grow to encompass all elements in the array

Implementation

We’ll use a maximum heap so we can always access the largest element in O(1) time

A heap can be represented using an array

Heapify is the operation to convert the unsorted array to a heap

We use the same array with no additional space to do the heapify

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474078#content

Max-heap heapify starting from the last parent in an unordered array

Max-heap heapify swaps for values 2, 5, 9, 56, 6, and 17

Max-heap heapify child checks and swaps involving 14, 6, 4, and 56

Final max-heap heapify swap of values 4 and 12

Completed max-heap tree with value 56 at the root

			
class MaxHeap<T: Comparable>: Heap {
    var array: [T?]
    var count: Int
    
    required init(_ input: [T]) {
        self.array = input
        self.count = input.count
    }
    
    //Recursive call
    func siftDown(index: Int) {
        let leftChildIndex = leftChildIndex(index: index)
        let rightChildIndex = rightChildIndex(index: index)
        
        //smaller value in chids
        var swapCandidateIndex: Int?
        if leftChildIndex != nil, rightChildIndex != nil {
            if array[leftChildIndex!]! > array[rightChildIndex!]! {
                swapCandidateIndex = leftChildIndex
            }
            else {
                swapCandidateIndex = rightChildIndex
            }
        }
        else if leftChildIndex != nil {
            swapCandidateIndex = leftChildIndex
        }
        else if rightChildIndex != nil {
            swapCandidateIndex = rightChildIndex
        }
        
        //Base case
        guard let swapCandidateIndex, let swapCandidateValue = array[swapCandidateIndex], let currentIndexValue = array[index] else {
            return
        }
        
        if currentIndexValue > swapCandidateValue {
            let value = array[swapCandidateIndex]
            //Sift down small value to the next level
            array[swapCandidateIndex] = currentIndexValue
            array[index] = swapCandidateValue
            
            //Recursive Call
            siftDown(index: swapCandidateIndex)
        }
    }
    
    func siftUp(index: Int) {
        guard let parentIndex = parentIndex(index: index), let currentValue = array[index] else {
            return
        }
        if array[parentIndex]! < currentValue {
            let parentValue = array[parentIndex]!
            array[parentIndex] = currentValue
            array[index] = parentValue
            siftUp(index: parentIndex)
        }
    }
    
    
    func insert(value: Item) {
        array.append(value)
        count = array.count
        let insertedIndex = array.count - 1
        siftUp(index: insertedIndex)
    }
    
    
    func removeHighestPriority() -> T? {
        let root = array[0]
        let lastElement = array[array.count - 1]
        array.removeFirst()
        array.insert(lastElement, at: 0)
        siftDown(index: 0)
        return root
    }
    
    //Heapify the entire array
    func heapify(index: Int) {
        //Start with the parent index of the last element
        guard var parentIndex = parentIndex(index: index) else {
            return
        }
        while parentIndex >= 0 {
            percolateDown(index: parentIndex)
            parentIndex -= 1
        }
    }
    
    func percolateDown(index: Int) {
        let leftIndex = leftChildIndex(index: index)
        let rightIndex = rightChildIndex(index: index)
        
        //Check If the max heap property is satisfied
        if let leftIndex, array[leftIndex]! > array[index]! {
            let currentValue = array[index]!
            let leftChildValue = array[leftIndex]!
            array[index] = leftChildValue
            array[leftIndex] = currentValue
            percolateDown(index: leftIndex)
        }
        if let rightIndex, array[rightIndex]! > array[index]! {
            let currentValue = array[index]!
            let rightChildValue = array[rightIndex]!
            array[index] = rightChildValue
            array[rightIndex] = currentValue
            percolateDown(index: rightIndex)
        }
    }
}
let input = [4, 6, 9, 2, 10, 56, 12, 5, 1, 17, 14]
let maxHeap = MaxHeap(input)
maxHeap.heapify(index: input.count - 1)
print(maxHeap.array)

		

Swift max-heap heapify implementation and output array

Heap Sort – Heap to Sorted Array

Heap-sort sequence swapping the maximum root with the array end

Full source – (This code has updated previous example)

			
protocol Heap {
    associatedtype Item: Comparable
    var array: [Item?] { get set }
    var count: Int { get set }
    
    init(_ input: [Item])
    
    func leftChildIndex(index: Int, endIndex: Int) -> Int?
    func rightChildIndex(index: Int, endIndex: Int) -> Int?
    func parentIndex(index: Int, endIndex: Int) -> Int?
    func siftDown(index: Int)
    func siftUp(index: Int)
    func insert(value: Item)
    func removeHighestPriority() -> Item?
}
extension Heap {
    func leftChildIndex(index: Int, endIndex: Int) -> Int? {
        let leftIndex = 2 * index + 1
        if leftIndex > endIndex {
            return nil
        }
        return leftIndex
    }
    
    func rightChildIndex(index: Int, endIndex: Int) -> Int? {
        let rightIndex = 2 * index + 2
        if rightIndex > endIndex {
            return nil
        }
        return rightIndex
    }
    
    func parentIndex(index: Int, endIndex: Int) -> Int? {
        if index < 0 || index > endIndex {
            return nil
        }
        return (index - 1) / 2
    }
    
    //MARK: Helper functions
    var isFull: Bool {
        count == array.count
    }
}
class MinHeap<T: Comparable>: Heap {
    var array: [T?]
    var count: Int
    
    required init(_ input: [T]) {
        self.array = input
        self.count = input.count
    }
    
    //Recursive call
    func siftDown(index: Int) {
        let leftChildIndex = leftChildIndex(index: index, endIndex: count)
        let rightChildIndex = rightChildIndex(index: index, endIndex: count)
        
        //smaller value in chids
        var swapCandidateIndex: Int?
        if leftChildIndex != nil, rightChildIndex != nil {
            if array[leftChildIndex!]! < array[rightChildIndex!]! {
                swapCandidateIndex = leftChildIndex
            }
            else {
                swapCandidateIndex = rightChildIndex
            }
        }
        else if leftChildIndex != nil {
            swapCandidateIndex = leftChildIndex
        }
        else if rightChildIndex != nil {
            swapCandidateIndex = rightChildIndex
        }
        
        //Base case
        guard let swapCandidateIndex, let swapCandidateValue = array[swapCandidateIndex], let currentIndexValue = array[index] else {
            return
        }
        
        if currentIndexValue > swapCandidateValue {
            let value = array[swapCandidateIndex]
            //Sift down large value to the next level
            array[swapCandidateIndex] = currentIndexValue
            array[index] = swapCandidateValue
            
            //Recursive Call
            siftDown(index: swapCandidateIndex)
        }
    }
    
    func siftUp(index: Int) {
        guard let parentIndex = parentIndex(index: index, endIndex: count), let currentValue = array[index] else {
            return
        }
        if array[parentIndex]! > currentValue {
            let parentValue = array[parentIndex]!
            array[parentIndex] = currentValue
            array[index] = parentValue
            siftUp(index: parentIndex)
        }
    }
    
    
    func insert(value: Item) {
        array.append(value)
        count = array.count
        let insertedIndex = array.count - 1
        siftUp(index: insertedIndex)
    }
    
    
    func removeHighestPriority() -> T? {
        let root = array[0]
        let lastElement = array[array.count - 1]
        array.removeFirst()
        array.insert(lastElement, at: 0)
        siftDown(index: 0)
        return root
    }
}
class MaxHeap<T: Comparable>: Heap {
    var array: [T?]
    var count: Int
    
    required init(_ input: [T]) {
        self.array = input
        self.count = input.count
    }
    
    //Recursive call
    func siftDown(index: Int) {
        let leftChildIndex = leftChildIndex(index: index, endIndex: count)
        let rightChildIndex = rightChildIndex(index: index, endIndex: count)
        
        //smaller value in chids
        var swapCandidateIndex: Int?
        if leftChildIndex != nil, rightChildIndex != nil {
            if array[leftChildIndex!]! > array[rightChildIndex!]! {
                swapCandidateIndex = leftChildIndex
            }
            else {
                swapCandidateIndex = rightChildIndex
            }
        }
        else if leftChildIndex != nil {
            swapCandidateIndex = leftChildIndex
        }
        else if rightChildIndex != nil {
            swapCandidateIndex = rightChildIndex
        }
        
        //Base case
        guard let swapCandidateIndex, let swapCandidateValue = array[swapCandidateIndex], let currentIndexValue = array[index] else {
            return
        }
        
        if currentIndexValue > swapCandidateValue {
            let value = array[swapCandidateIndex]
            //Sift down small value to the next level
            array[swapCandidateIndex] = currentIndexValue
            array[index] = swapCandidateValue
            
            //Recursive Call
            siftDown(index: swapCandidateIndex)
        }
    }
    
    func siftUp(index: Int) {
        guard let parentIndex = parentIndex(index: index, endIndex: count), let currentValue = array[index] else {
            return
        }
        if array[parentIndex]! < currentValue {
            let parentValue = array[parentIndex]!
            array[parentIndex] = currentValue
            array[index] = parentValue
            siftUp(index: parentIndex)
        }
    }
    
    
    func insert(value: Item) {
        array.append(value)
        count = array.count
        let insertedIndex = array.count - 1
        siftUp(index: insertedIndex)
    }
    
    
    func removeHighestPriority() -> T? {
        let root = array[0]
        let lastElement = array[array.count - 1]
        array.removeFirst()
        array.insert(lastElement, at: 0)
        siftDown(index: 0)
        return root
    }
    
    //Heapify the entire array
    func heapify(index: Int) {
        //Start with the parent index of the last element
        guard var parentIndex = parentIndex(index: index, endIndex: index) else {
            return
        }
        while parentIndex >= 0 {
            percolateDown(index: parentIndex, endIndex: index)
            parentIndex -= 1
        }
    }
    
    func percolateDown(index: Int, endIndex: Int) {
        let leftIndex = leftChildIndex(index: index, endIndex: endIndex)
        let rightIndex = rightChildIndex(index: index, endIndex: endIndex)
        
        //Check If the max heap property is satisfied
        if let leftIndex, array[leftIndex]! > array[index]! {
            let currentValue = array[index]!
            let leftChildValue = array[leftIndex]!
            array[index] = leftChildValue
            array[leftIndex] = currentValue
            percolateDown(index: leftIndex, endIndex: endIndex)
        }
        if let rightIndex, array[rightIndex]! > array[index]! {
            let currentValue = array[index]!
            let rightChildValue = array[rightIndex]!
            array[index] = rightChildValue
            array[rightIndex] = currentValue
            percolateDown(index: rightIndex, endIndex: endIndex)
        }
    }
    
    func heapSort() {
        //Heapify! The entire unsorted array so It's now a Heap
        heapify(index: array.count - 1)
        var lastIndex = array.count - 1
        while lastIndex > 0 {
            let maxValue = array[0]!
            let currentValue = array[lastIndex]!
            //Swap - Start with the very last index, and place the largest element in the last position
            array[0] = currentValue
            array[lastIndex] = maxValue
            
            //Count down because last element already sorted
            lastIndex -= 1
            percolateDown(index: 0, endIndex: lastIndex)
        }
    }
}
let input = [4, 6, 9, 2, 10, 56, 12, 5, 1, 17, 14]
let maxHeap = MaxHeap(input)
print("Heapify - Make unordered input to maxHeap: ")
maxHeap.heapify(index: input.count - 1)
print(maxHeap.array)
maxHeap.heapSort()
print("\nHeap Sort!: ")
print(maxHeap.array)

		

Swift heapSort implementation showing heapified and sorted arrays

Heap Sort

Heap sort uses operations on a heap to get a sorted list

Insertion into a heap is done N times to get all the elements in heap form

Removal of the maximum element is done N times, followed by Heapify

Insertion and removal have log N time complexity so doing it for N elements means

The average case complexity of heap sort is O(nLogN)

Heap sort is not adaptive – If works on almost sorted array it’s not a fast because there is no way to break up early.

It’s not a stable sort – If there is 2 same value.. that order is not maintain in heap sort. It means 2 same value can’t guarantee orders. (But heap sort can handle if there are same values) see stackoverflow

It does not need additional space – Space complexity is O(1)
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474084#content

My example codes for Heap Structure is not the same. Some exercise I used the fixed array using maxSize. The others are not. Please check full source code at each exercise.

Exercise 1. Find the maximum element in a minimum heap

Finding the maximum value in a min-heap by checking its leaf nodes

			
class MinHeap<T: Comparable>: Heap {
    var array: [T?]
    var count: Int
    
    required init(_ input: [T]) {
        self.array = input
        self.count = input.count
    }
    
    //Recursive call
    func siftDown(index: Int) {
        let leftChildIndex = leftChildIndex(index: index, endIndex: count)
        let rightChildIndex = rightChildIndex(index: index, endIndex: count)
        
        //smaller value in chids
        var swapCandidateIndex: Int?
        if leftChildIndex != nil, rightChildIndex != nil {
            if array[leftChildIndex!]! < array[rightChildIndex!]! {
                swapCandidateIndex = leftChildIndex
            }
            else {
                swapCandidateIndex = rightChildIndex
            }
        }
        else if leftChildIndex != nil {
            swapCandidateIndex = leftChildIndex
        }
        else if rightChildIndex != nil {
            swapCandidateIndex = rightChildIndex
        }
        
        //Base case
        guard let swapCandidateIndex, let swapCandidateValue = array[swapCandidateIndex], let currentIndexValue = array[index] else {
            return
        }
        
        if currentIndexValue > swapCandidateValue {
            let value = array[swapCandidateIndex]
            //Sift down large value to the next level
            array[swapCandidateIndex] = currentIndexValue
            array[index] = swapCandidateValue
            
            //Recursive Call
            siftDown(index: swapCandidateIndex)
        }
    }
    
    func siftUp(index: Int) {
        guard let parentIndex = parentIndex(index: index, endIndex: count), let currentValue = array[index] else {
            return
        }
        if array[parentIndex]! > currentValue {
            let parentValue = array[parentIndex]!
            array[parentIndex] = currentValue
            array[index] = parentValue
            siftUp(index: parentIndex)
        }
    }
    
    
    func insert(value: Item) {
        array.append(value)
        count = array.count
        let insertedIndex = array.count - 1
        siftUp(index: insertedIndex)
    }
    
    
    func removeHighestPriority() -> T? {
        let root = array[0]
        let lastElement = array[array.count - 1]
        array.removeFirst()
        array.insert(lastElement, at: 0)
        siftDown(index: 0)
        return root
    }
    
    //Heapify the entire array
    func heapify(index: Int) {
        //Start with the parent index of the last element
        guard var parentIndex = parentIndex(index: index, endIndex: index) else {
            return
        }
        while parentIndex >= 0 {
            percolateDown(index: parentIndex, endIndex: index)
            parentIndex -= 1
        }
    }
    
    func percolateDown(index: Int, endIndex: Int) {
        let leftIndex = leftChildIndex(index: index, endIndex: endIndex)
        let rightIndex = rightChildIndex(index: index, endIndex: endIndex)
        
        //Check If the max heap property is satisfied
        if let leftIndex, array[leftIndex]! < array[index]! {
            let currentValue = array[index]!
            let leftChildValue = array[leftIndex]!
            array[index] = leftChildValue
            array[leftIndex] = currentValue
            percolateDown(index: leftIndex, endIndex: endIndex)
        }
        if let rightIndex, array[rightIndex]! < array[index]! {
            let currentValue = array[index]!
            let rightChildValue = array[rightIndex]!
            array[index] = rightChildValue
            array[rightIndex] = currentValue
            percolateDown(index: rightIndex, endIndex: endIndex)
        }
    }
    
    func maxValue() -> T? {
        let lastIndex = array.count - 1
        guard let parentIndex = parentIndex(index: lastIndex, endIndex: array.count - 1), var maxValue = array[parentIndex + 1] else {
            return nil
        }
        //maxValue is first leaf node
        let firstLeafIndex = parentIndex + 1
        for i in firstLeafIndex..<array.count {
            maxValue = max(array[i]!, maxValue)
        }
        return maxValue
    }
}
let input = [4, 6, 9, 2, 10, 56, 12, 5, 1, 17, 14]
let minHeap = MinHeap(input)
print("Heapify - Make unordered input to maxHeap: ")
minHeap.heapify(index: input.count - 1)
print(minHeap.array)
print("🟢 Max Value in MinHeap: \(minHeap.maxValue())")

		

Swift min-heap maximum lookup returning value 56

Exercise 2. Find K Largest Elements in a Stream

Stream can be events from external sources. It is not a sorted

Use a minimum heap with size K to store elements as they come in

The top of the heap will have the smallest of the K elements stored in the heap

If the new elements in the stream is larger than the minimum – add it to the heap

The heap will always have the largest K elements from the stream
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474098?start=150#content

Finding the K largest stream values with a fixed-size min-heap

K-largest stream processing that replaces the min-heap root with larger values

Final K-largest stream updates producing a heap of the largest values

			
protocol Heap {
    associatedtype Item: Comparable
    var array: [Item?] { get set }
    var count: Int { get set }
    var maxSize: Int { get set }
    
    init(maxSize: Int)
    
    func leftChildIndex(index: Int, endIndex: Int) -> Int?
    func rightChildIndex(index: Int, endIndex: Int) -> Int?
    func parentIndex(index: Int, endIndex: Int) -> Int?
    func siftDown(index: Int)
    func siftUp(index: Int)
    func insert(value: Item)
    func removeHighestPriority() -> Item?
    func highestPriority() -> Item?
}
extension Heap {
    func leftChildIndex(index: Int, endIndex: Int) -> Int? {
        let leftIndex = 2 * index + 1
        if leftIndex > endIndex {
            return nil
        }
        return leftIndex
    }
    
    func rightChildIndex(index: Int, endIndex: Int) -> Int? {
        let rightIndex = 2 * index + 2
        if rightIndex > endIndex {
            return nil
        }
        return rightIndex
    }
    
    func parentIndex(index: Int, endIndex: Int) -> Int? {
        if index < 0 || index > endIndex {
            return nil
        }
        return (index - 1) / 2
    }
    
    //MARK: Helper functions
    var isFull: Bool {
        count == array.count
    }
    
    func highestPriority() -> Item? {
        guard count > 0, let firstItem = array.first else {
            return nil
        }
        return firstItem
    }
}
class MinHeap<T: Comparable>: Heap {
    var array: [T?]
    var count: Int
    var maxSize: Int
    
    required init(maxSize: Int) {
        self.array = Array(repeating: nil, count: maxSize)
        self.count = 0
        self.maxSize = maxSize
    }
    
    //Recursive call
    func siftDown(index: Int) {
        let endIndex = min(count, maxSize)
        let leftChildIndex = leftChildIndex(index: index, endIndex: endIndex)
        let rightChildIndex = rightChildIndex(index: index, endIndex: endIndex)
        
        //smaller value in chids
        var swapCandidateIndex: Int?
        if leftChildIndex != nil, rightChildIndex != nil {
            if array[leftChildIndex!]! < array[rightChildIndex!]! {
                swapCandidateIndex = leftChildIndex
            }
            else {
                swapCandidateIndex = rightChildIndex
            }
        }
        else if leftChildIndex != nil {
            swapCandidateIndex = leftChildIndex
        }
        else if rightChildIndex != nil {
            swapCandidateIndex = rightChildIndex
        }
        
        //Base case
        guard let swapCandidateIndex, let swapCandidateValue = array[swapCandidateIndex], let currentIndexValue = array[index] else {
            return
        }
        
        if currentIndexValue > swapCandidateValue {
            let value = array[swapCandidateIndex]
            //Sift down large value to the next level
            array[swapCandidateIndex] = currentIndexValue
            array[index] = swapCandidateValue
            
            //Recursive Call
            siftDown(index: swapCandidateIndex)
        }
    }
    
    func siftUp(index: Int) {
        let endIndex = min(count, maxSize)
        guard let parentIndex = parentIndex(index: index, endIndex: endIndex), let currentValue = array[index] else {
            return
        }
        if array[parentIndex]! > currentValue {
            let parentValue = array[parentIndex]!
            array[parentIndex] = currentValue
            array[index] = parentValue
            siftUp(index: parentIndex)
        }
    }
    
    
    func insert(value: Item) {
        //MARK: Check isHeap Full or not
        if count >= array.count {
            return
        }
        array[count] = value
        let insertedIndex = count
        siftUp(index: insertedIndex)
        count += 1
    }
    
    
    func removeHighestPriority() -> T? {
        let root = array[0]
        let lastElement = array[count - 1]
        array.removeFirst()
        array.insert(lastElement, at: 0)
        count -= 1
        siftDown(index: 0)
        return root
    }
    
    //Heapify the entire array
    func heapify(index: Int) {
        //Start with the parent index of the last element
        guard var parentIndex = parentIndex(index: index, endIndex: index) else {
            return
        }
        while parentIndex >= 0 {
            percolateDown(index: parentIndex, endIndex: index)
            parentIndex -= 1
        }
    }
    
    func percolateDown(index: Int, endIndex: Int) {
        let leftIndex = leftChildIndex(index: index, endIndex: endIndex)
        let rightIndex = rightChildIndex(index: index, endIndex: endIndex)
        
        //Check If the max heap property is satisfied
        if let leftIndex, array[leftIndex]! < array[index]! {
            let currentValue = array[index]!
            let leftChildValue = array[leftIndex]!
            array[index] = leftChildValue
            array[leftIndex] = currentValue
            percolateDown(index: leftIndex, endIndex: endIndex)
        }
        if let rightIndex, array[rightIndex]! < array[index]! {
            let currentValue = array[index]!
            let rightChildValue = array[rightIndex]!
            array[index] = rightChildValue
            array[rightIndex] = currentValue
            percolateDown(index: rightIndex, endIndex: endIndex)
        }
    }
    
    func maxValue() -> T? {
        let lastIndex = array.count - 1
        guard let parentIndex = parentIndex(index: lastIndex, endIndex: array.count - 1), var maxValue = array[parentIndex + 1] else {
            return nil
        }
        //maxValue is first leaf node
        let firstLeafIndex = parentIndex + 1
        for i in firstLeafIndex..<array.count {
            maxValue = max(array[i]!, maxValue)
        }
        return maxValue
    }
}
func findKLargestElement() {
    let input = [4, 6, 9, 2, 10, 56, 12, 5, 1, 17, 14]
    let minHeap = MinHeap<Int>(maxSize: 5)
    for data in input {
        if !minHeap.isFull {
            minHeap.insert(value: data)
        }
        else {
            //heap is full
            if let minValue = minHeap.highestPriority(),
                minValue < data {
                minHeap.removeHighestPriority()
                minHeap.insert(value: data)
            }
        }
    }
    
    print(minHeap.array)
    print("🟢 Max Value in MinHeap: \(minHeap.maxValue())")
}
findKLargestElement()

		

Swift findKLargestElement implementation and final five-value min-heap

Exercise 3. Merge K sorted arrays using heaps

Say the lists to be merged are sorted in ascending order

Remove the smallest element from each list and add it to the minimum heap – There will be K elements in the Heap

Get the minimum element from the heap – It will be the smallest of all first elements in the K lists

Keep track of which list this smallest element originally came from

Get the next smallest element from the same list

Continue this till the sorted list is completely filled
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474102#content

Merging K sorted arrays with a min-heap of capacity three

K-way merge steps that extract the minimum and insert the next list value

Final K-way merge steps inserting values 13 and 6 into the heap

As you can see when removed minValue then keep insert newValue from minValue’s original array.

			
protocol Heap {
    associatedtype Item: Comparable
    var array: [Item?] { get set }
    var count: Int { get set }
    var maxSize: Int { get set }
    
    init(maxSize: Int)
    
    func leftChildIndex(index: Int, endIndex: Int) -> Int?
    func rightChildIndex(index: Int, endIndex: Int) -> Int?
    func parentIndex(index: Int, endIndex: Int) -> Int?
    func siftDown(index: Int)
    func siftUp(index: Int)
    func insert(value: Item)
    func removeHighestPriority() -> Item?
    func highestPriority() -> Item?
}
extension Heap {
    func leftChildIndex(index: Int, endIndex: Int) -> Int? {
        let leftIndex = 2 * index + 1
        if leftIndex > endIndex {
            return nil
        }
        return leftIndex
    }
    
    func rightChildIndex(index: Int, endIndex: Int) -> Int? {
        let rightIndex = 2 * index + 2
        if rightIndex > endIndex {
            return nil
        }
        return rightIndex
    }
    
    func parentIndex(index: Int, endIndex: Int) -> Int? {
        if index < 0 || index > endIndex {
            return nil
        }
        return (index - 1) / 2
    }
    
    //MARK: Helper functions
    var isFull: Bool {
        count == array.count
    }
    
    func highestPriority() -> Item? {
        guard count > 0, let firstItem = array.first else {
            return nil
        }
        return firstItem
    }
}
class MinHeap<T: Comparable>: Heap {
    var array: [T?]
    var count: Int
    var maxSize: Int
    
    required init(maxSize: Int) {
        self.array = Array(repeating: nil, count: maxSize)
        self.count = 0
        self.maxSize = maxSize
    }
    
    //Recursive call
    func siftDown(index: Int) {
        let endIndex = min(count, maxSize)
        let leftChildIndex = leftChildIndex(index: index, endIndex: endIndex)
        let rightChildIndex = rightChildIndex(index: index, endIndex: endIndex)
        
        //smaller value in chids
        var swapCandidateIndex: Int?
        if leftChildIndex != nil, rightChildIndex != nil {
            if array[leftChildIndex!]! < array[rightChildIndex!]! {
                swapCandidateIndex = leftChildIndex
            }
            else {
                swapCandidateIndex = rightChildIndex
            }
        }
        else if leftChildIndex != nil {
            swapCandidateIndex = leftChildIndex
        }
        else if rightChildIndex != nil {
            swapCandidateIndex = rightChildIndex
        }
        
        //Base case
        guard let swapCandidateIndex, let swapCandidateValue = array[swapCandidateIndex], let currentIndexValue = array[index] else {
            return
        }
        
        if currentIndexValue > swapCandidateValue {
            let value = array[swapCandidateIndex]
            //Sift down large value to the next level
            array[swapCandidateIndex] = currentIndexValue
            array[index] = swapCandidateValue
            
            //Recursive Call
            siftDown(index: swapCandidateIndex)
        }
    }
    
    func siftUp(index: Int) {
        let endIndex = min(count, maxSize)
        guard let parentIndex = parentIndex(index: index, endIndex: endIndex), let currentValue = array[index] else {
            return
        }
        if array[parentIndex]! > currentValue {
            let parentValue = array[parentIndex]!
            array[parentIndex] = currentValue
            array[index] = parentValue
            siftUp(index: parentIndex)
        }
    }
    
    
    func insert(value: Item) {
        //MARK: Check isHeap Full or not
        if count >= array.count {
            return
        }
        array[count] = value
        let insertedIndex = count
        siftUp(index: insertedIndex)
        count += 1
    }
    
    
    func removeHighestPriority() -> T? {
        let root = array[0]
        let lastElement = array[count - 1]
        array.removeFirst()
        array.insert(lastElement, at: 0)
        count -= 1
        siftDown(index: 0)
        return root
    }
    
    //Heapify the entire array
    func heapify(index: Int) {
        //Start with the parent index of the last element
        guard var parentIndex = parentIndex(index: index, endIndex: index) else {
            return
        }
        while parentIndex >= 0 {
            percolateDown(index: parentIndex, endIndex: index)
            parentIndex -= 1
        }
    }
    
    func percolateDown(index: Int, endIndex: Int) {
        let leftIndex = leftChildIndex(index: index, endIndex: endIndex)
        let rightIndex = rightChildIndex(index: index, endIndex: endIndex)
        
        //Check If the max heap property is satisfied
        if let leftIndex, array[leftIndex]! < array[index]! {
            let currentValue = array[index]!
            let leftChildValue = array[leftIndex]!
            array[index] = leftChildValue
            array[leftIndex] = currentValue
            percolateDown(index: leftIndex, endIndex: endIndex)
        }
        if let rightIndex, array[rightIndex]! < array[index]! {
            let currentValue = array[index]!
            let rightChildValue = array[rightIndex]!
            array[index] = rightChildValue
            array[rightIndex] = currentValue
            percolateDown(index: rightIndex, endIndex: endIndex)
        }
    }
    
    func maxValue() -> T? {
        let lastIndex = array.count - 1
        guard let parentIndex = parentIndex(index: lastIndex, endIndex: array.count - 1), var maxValue = array[parentIndex + 1] else {
            return nil
        }
        //maxValue is first leaf node
        let firstLeafIndex = parentIndex + 1
        for i in firstLeafIndex..<array.count {
            maxValue = max(array[i]!, maxValue)
        }
        return maxValue
    }
}
class Element: Comparable {
    let listIndex: Int
    let value: Int
    
    init(listIndex: Int, value: Int) {
        self.listIndex = listIndex
        self.value = value
    }
    
    static func < (lhs: Element, rhs: Element) -> Bool {
        lhs.value < rhs.value
    }
    
    static func == (lhs: Element, rhs: Element) -> Bool {
        lhs.value == rhs.value
    }
}
//Lists is sorted lists ascending orders
func mergeKSortedList(total: Int, lists: [[Int]]) {
    let minHeap = MinHeap<Element>(maxSize: lists.count)
    var result = [Int]()
    var tempLists = lists
    
    //First step - Filled minHeap
    for i in 0..<lists.count {
        var list = tempLists[i]
        if !list.isEmpty {
            let minValue = tempLists[i].removeFirst()
            minHeap.insert(value: Element(listIndex: i, value: minValue))
        }
    }
    
    while result.count < total {
        guard let minElement = minHeap.removeHighestPriority() else {
            break
        }
        result.append(minElement.value)
        if !tempLists[minElement.listIndex].isEmpty {
            let nextInsertElement = tempLists[minElement.listIndex].removeFirst()
            minHeap.insert(value: Element(listIndex: minElement.listIndex, value: nextInsertElement))
        }
    }
    print("K Merged Sorted Array: \(result)")
}
mergeKSortedList(total: 13, lists: [
    [5, 6, 7, 9, 10],
    [2, 3, 13, 15, 17, 20],
    [1, 8]
])

		

Swift K-way merge output sorted as 1, 2, 3, 5, 6, 7, 8, 9, 10, 13, 15, 17, 20

Exercise 4. Find the median in a stream of elements

The stream implies that we have no idea which elements are going in to come in next – We have to keep track of the median as the elements stream in

Use a Max Heap to store the smaller (First) Half of elements seen in the stream

Use a Min Heap to store the larger (Second) Half of elements seen in the stream

Now if the size of these heaps are such that they differ by no more than 1 element.

Then the minimum element of the min heap and the maximum element of the maximum heap are the middle elements of the stream

Getting the median is then a simple calculation
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8474108#content

Streaming median setup that inserts 5 into a max-heap and 6 and 7 into a min-heap

Streaming median updates that insert 9, rebalance 6, and then insert 10

Balanced max-heap and min-heap used to calculate the stream median

Heap Implementation

			
enum HeapType {
    case min
    case max
}
protocol Heap {
    associatedtype Item: Comparable
    var array: [Item?] { get set }
    var count: Int { get set }
    var maxSize: Int? { get set }
    var endIndex: Int { get }
    
    init(maxSize: Int?, type: HeapType)
    
    func leftChildIndex(index: Int, endIndex: Int) -> Int?
    func rightChildIndex(index: Int, endIndex: Int) -> Int?
    func parentIndex(index: Int, endIndex: Int) -> Int?
    func siftDown(index: Int)
    func siftUp(index: Int)
    func insert(value: Item)
    func removeHighestPriority() -> Item?
    func highestPriority() -> Item?
}
extension Heap {
    func leftChildIndex(index: Int, endIndex: Int) -> Int? {
        let leftIndex = 2 * index + 1
        if leftIndex >= endIndex {
            return nil
        }
        return leftIndex
    }
    
    func rightChildIndex(index: Int, endIndex: Int) -> Int? {
        let rightIndex = 2 * index + 2
        if rightIndex >= endIndex {
            return nil
        }
        return rightIndex
    }
    
    func parentIndex(index: Int, endIndex: Int) -> Int? {
        if index < 0 || index >= endIndex {
            return nil
        }
        return (index - 1) / 2
    }
    
    //MARK: Helper functions
    var isFull: Bool {
        count == array.count
    }
    
    func highestPriority() -> Item? {
        guard count > 0, let firstItem = array.first else {
            return nil
        }
        return firstItem
    }
}

		

			
class HeapStructure<T: Comparable>: Heap {
    var array: [T?]
    var count: Int
    var maxSize: Int?
    private let type: HeapType
    
    required init(maxSize: Int?, type: HeapType) {
        if let maxSize {
            self.array = Array(repeating: nil, count: maxSize)
        }
        else {
            self.array = [T?]()
        }
        self.type = type
        self.count = 0
        self.maxSize = maxSize
    }
    
    var endIndex: Int {
        if let maxSize {
            return min(count, maxSize)
        }
        return count
    }
    
    //Recursive call
    func siftDown(index: Int) {
        let leftChildIndex = leftChildIndex(index: index, endIndex: endIndex)
        let rightChildIndex = rightChildIndex(index: index, endIndex: endIndex)
        //smaller value in chids
        var swapCandidateIndex: Int?
        if leftChildIndex != nil, rightChildIndex != nil {
            switch type {
            case .min:
                if array[leftChildIndex!]! < array[rightChildIndex!]! {
                    swapCandidateIndex = leftChildIndex
                }
                else {
                    swapCandidateIndex = rightChildIndex
                }
            case .max:
                if array[leftChildIndex!]! > array[rightChildIndex!]! {
                    swapCandidateIndex = leftChildIndex
                }
                else {
                    swapCandidateIndex = rightChildIndex
                }
            }
        }
        else if leftChildIndex != nil {
            swapCandidateIndex = leftChildIndex
        }
        else if rightChildIndex != nil {
            swapCandidateIndex = rightChildIndex
        }
        //Base case
        guard let swapCandidateIndex, let swapCandidateValue = array[swapCandidateIndex], let currentIndexValue = array[index] else {
            return
        }
        
        switch type {
        case .min:
            if currentIndexValue > swapCandidateValue {
                let value = array[swapCandidateIndex]
                //Sift down large value to the next level
                array[swapCandidateIndex] = currentIndexValue
                array[index] = swapCandidateValue
                
                //Recursive Call
                siftDown(index: swapCandidateIndex)
            }
        case .max:
            if currentIndexValue < swapCandidateValue {
                let value = array[swapCandidateIndex]
                //Sift down large value to the next level
                array[swapCandidateIndex] = currentIndexValue
                array[index] = swapCandidateValue
                
                //Recursive Call
                siftDown(index: swapCandidateIndex)
            }
        }
    }
    
    func siftUp(index: Int) {
        guard let parentIndex = parentIndex(index: index, endIndex: endIndex), let currentValue = array[index] else {
            return
        }
        switch type {
        case .min:
            if array[parentIndex]! > currentValue {
                let parentValue = array[parentIndex]!
                array[parentIndex] = currentValue
                array[index] = parentValue
                siftUp(index: parentIndex)
            }
        case .max:
            if array[parentIndex]! < currentValue {
                let parentValue = array[parentIndex]!
                array[parentIndex] = currentValue
                array[index] = parentValue
                siftUp(index: parentIndex)
            }
        }
    }
    
    func insert(value: Item) {
        if let maxSize {
            array[count] = value
            let insertedIndex = count
            count += 1
            siftUp(index: insertedIndex)
        }
        else {
            array.append(value)
            let insertedIndex = array.count - 1
            count += 1
            siftUp(index: insertedIndex)
        }
    }
    
    
    func removeHighestPriority() -> T? {
        let root = array[0]
        //Remove First elements
        array.removeFirst()
        count -= 1
        array.swapAt(0, count - 1)
        siftDown(index: 0)
        return root
    }
    
    //Heapify the entire array
    func heapify(index: Int) {
        //Start with the parent index of the last element
        guard var parentIndex = parentIndex(index: index, endIndex: index) else {
            return
        }
        while parentIndex >= 0 {
            percolateDown(index: parentIndex, endIndex: index)
            parentIndex -= 1
        }
    }
    
    func percolateDown(index: Int, endIndex: Int) {
        let leftIndex = leftChildIndex(index: index, endIndex: endIndex)
        let rightIndex = rightChildIndex(index: index, endIndex: endIndex)
        
        switch type {
        case .min:
            //Check If the Min heap property is satisfied
            if let leftIndex, array[leftIndex]! < array[index]! {
                let currentValue = array[index]!
                let leftChildValue = array[leftIndex]!
                array[index] = leftChildValue
                array[leftIndex] = currentValue
                percolateDown(index: leftIndex, endIndex: endIndex)
            }
            if let rightIndex, array[rightIndex]! < array[index]! {
                let currentValue = array[index]!
                let rightChildValue = array[rightIndex]!
                array[index] = rightChildValue
                array[rightIndex] = currentValue
                percolateDown(index: rightIndex, endIndex: endIndex)
            }
        case .max:
            //Check If the Max heap property is satisfied
            if let leftIndex, array[leftIndex]! > array[index]! {
                let currentValue = array[index]!
                let leftChildValue = array[leftIndex]!
                array[index] = leftChildValue
                array[leftIndex] = currentValue
                percolateDown(index: leftIndex, endIndex: endIndex)
            }
            if let rightIndex, array[rightIndex]! > array[index]! {
                let currentValue = array[index]!
                let rightChildValue = array[rightIndex]!
                array[index] = rightChildValue
                array[rightIndex] = currentValue
                percolateDown(index: rightIndex, endIndex: endIndex)
            }
        }
    }
}

		

			
let minHeap = HeapStructure<Int>(maxSize: nil, type: .min)
let maxHeap = HeapStructure<Int>(maxSize: nil, type: .max)
func getMedianValue(input: Int) -> Int {
    if maxHeap.count != 0, let maxValue = maxHeap.highestPriority(), input > maxValue {
        minHeap.insert(value: input)
        print("Insert \(input) > \(maxValue) to MinHeap")
    }
    else {
        maxHeap.insert(value: input)
        print("Insert \(input) to MaxHeap")
    }
    
    //Check rebalance - Difference is greater 1
    if maxHeap.count > minHeap.count, maxHeap.count - minHeap.count > 1, let _ = maxHeap.highestPriority() {
        let removedMaxValue = maxHeap.removeHighestPriority()!
        minHeap.insert(value: removedMaxValue)
        print("✅ Rebalanced - Insert removed: \(removedMaxValue) to MinHeap")
    }
    else if minHeap.count > maxHeap.count, minHeap.count - maxHeap.count > 1, let minValue = minHeap.highestPriority() {
        let removedMinValue = minHeap.removeHighestPriority()!
        maxHeap.insert(value: removedMinValue)
        
        print("✅ Rebalanced - Insert removed: \(removedMinValue) to MaxHeap")
    }
    
    if minHeap.count == maxHeap.count {
        return (minHeap.highestPriority()! + maxHeap.highestPriority()!) / 2
    }
    
    return minHeap.count > maxHeap.count ? minHeap.highestPriority()! : maxHeap.highestPriority()!
}
let input = [5, 6, 7, 9, 10, 2, 3, 13, 15, 17, 20, 1, 8]
for i in input {
    getMedianValue(input: i)
}
print("MinHeap: \(minHeap.array)")
print("MaxHeap: \(maxHeap.array)")

		

Swift streaming-median execution with the final min-heap and max-heap

Tip: Real Interview using Swift

Heap data structure is not part of Foundation. It means you need to implement heap if you want to solve Heap related problems.

It’s not easy. Implementing Heap in 1 hour interview is not make sense. You can see Apple’s official Heap data structure

Apple Collections Heap complexity table and benchmark chart

You can use array and sort items when insert value. Let’s call it FakeHeap!

FakeHeap source code

			
class FakeMinHeap {
    var array: [Int?]
    let maxSize: Int?
    init(maxSize: Int?) {
        self.maxSize = maxSize
        if let maxSize {
            array = Array(repeating: nil, count: maxSize)
        }
        else {
            array = [Int?]()
        }
    }
    
    var count: Int {
        array.count
    }
    
    func insert(value: Int) {
        array.append(value)
        array = array.compactMap { $0 }.sorted(by: <)
    }
    
    func highestPriority() -> Int? {
        return array.first ?? nil
    }
    
    func removeHighestPriority() -> Int? {
        return array.removeFirst()
    }
}
class FakeMaxHeap {
    var array: [Int?]
    let maxSize: Int?
    init(maxSize: Int?) {
        self.maxSize = maxSize
        if let maxSize {
            array = Array(repeating: nil, count: maxSize)
        }
        else {
            array = [Int?]()
        }
    }
    
    var count: Int {
        array.count
    }
    
    func insert(value: Int) {
        array.append(value)
        array = array.compactMap { $0 }.sorted(by: >)
    }
    
    func highestPriority() -> Int? {
        return array.first ?? nil
    }
    
    func removeHighestPriority() -> Int? {
        return array.removeFirst()
    }
}
let minHeap = FakeMinHeap(maxSize: nil)
let maxHeap = FakeMaxHeap(maxSize: nil)

		

Let’s test last exercise. Find the median in a stream of elements using FakeHeap!

			
let minHeap = FakeMinHeap(maxSize: nil)
let maxHeap = FakeMaxHeap(maxSize: nil)
func getMedianValue(input: Int) -> Int {
    if maxHeap.count != 0, let maxValue = maxHeap.highestPriority(), input > maxValue {
        minHeap.insert(value: input)
        print("Insert \(input) > \(maxValue) to MinHeap")
    }
    else {
        maxHeap.insert(value: input)
        print("Insert \(input) to MaxHeap")
    }
    
    //Check rebalance - Difference is greater 1
    if maxHeap.count > minHeap.count, maxHeap.count - minHeap.count > 1, let _ = maxHeap.highestPriority() {
        let removedMaxValue = maxHeap.removeHighestPriority()!
        minHeap.insert(value: removedMaxValue)
        print("✅ Rebalanced - Insert removed: \(removedMaxValue) to MinHeap")
    }
    else if minHeap.count > maxHeap.count, minHeap.count - maxHeap.count > 1, let minValue = minHeap.highestPriority() {
        let removedMinValue = minHeap.removeHighestPriority()!
        maxHeap.insert(value: removedMinValue)
        
        print("✅ Rebalanced - Insert removed: \(removedMinValue) to MaxHeap")
    }
    
    if minHeap.count == maxHeap.count {
        return (minHeap.highestPriority()! + maxHeap.highestPriority()!) / 2
    }
    
    return minHeap.count > maxHeap.count ? minHeap.highestPriority()! : maxHeap.highestPriority()!
}
let input = [5, 6, 7, 9, 10, 2, 3, 13, 15, 17, 20, 1, 8]
for i in input {
    getMedianValue(input: i)
}
print("MinHeap: \(minHeap.array)")
print("MaxHeap: \(maxHeap.array)")

		

Swift streaming-median output after rebalancing the min-heap and max-heap

As you can see, result is the same as Real Heap. (Absolutely time complexity is different compare with real heap data structure, because It’s fake heap to solve problem during the interview)

Comments

One response to “iOS, Heap Data Structure”

August 10, 2024

Turned 40 and got layoff on April fools day 2024, Here is my senior iOS interview experience with Google, Meta and Amazon – Shawn

[…] iOS, Heap Data Structure iOS, Graph(unweighted and weighted) – Shortest Path Algorithms (Dijkstra, Bellman-Ford) […]

Loading…