Shawn

iOS, Heap Data Structure

Published by

Traveller

on

✍️ 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

Shape Property, Height

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

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

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)

HEAPIFY – Sift Up

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)
        }
    }

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)
}

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
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
}

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
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)

Heap Sort – Heap to Sorted Array

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)

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

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())")

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
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()

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

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]
])

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

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)")

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

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)")

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)

댓글 남기기

Previous Post
Next Post