Heap data structure implementation in swift

Last Updated : 18 May, 2023

A heap is a complete binary tree where each node satisfies the heap property. The heap property is different for different types of heaps but, in general, it means that each node has a value that is greater than or equal to (or less than or equal to) the values of its children nodes.

Heaps are commonly used to implement priority queues, as they allow efficient insertion and removal of elements with the highest (or lowest) priority.

Types of Heap Data Structure:

Max Heap

Each node has a value that is greater than or equal to the values of its children nodes. The maximum value is always at the root of the heap.

Min Heap

Each node has a value that is less than or equal to the values of its children nodes. The minimum value is always at the root of the heap.

Below are the steps involved in the implementation of Max Heap:

Choose the type of heap: either min heap or max heap.
Create a class for the heap.
Create an array to hold the elements of the heap.
Implement the insert function to add new elements to the heap.
Implement the remove function to remove and return the top element from the heap.
Implement the peek function to return the top element of the heap without removing it.
Implement the isEmpty property to check if the heap is empty.

Here is the implementation of the max heap data structure in Swift:

Swift

// Swift code for the above approach: 
class MaxHeap<T: Comparable> { 
    var heap: [T] = [] 
      
    // Insert a new element into the heap 
    func insert(_ element: T) { 
        heap.append(element) 
        var currentIndex = heap.count - 1 
          
        // Bubble up the element until the 
        // heap property is restored 
        while currentIndex > 0 && heap[currentIndex] > heap[(currentIndex-1)/2] { 
            heap.swapAt(currentIndex, (currentIndex-1)/2) 
            currentIndex = (currentIndex-1)/2 
        } 
    } 
      
    // Remove and return the top 
    // element of the heap 
    func remove() -> T? { 
        guard !heap.isEmpty else { 
            return nil
        } 
          
        let topElement = heap[0] 
          
        if heap.count == 1 { 
            heap.removeFirst() 
        } else { 
            
            // Replace the top element  
            // with the last element in 
            // the heap 
            heap[0] = heap.removeLast() 
            var currentIndex = 0 
              
            // Bubble down the element until 
            // the heap property is restored 
            while true { 
                let leftChildIndex = 2*currentIndex+1 
                let rightChildIndex = 2*currentIndex+2 
                  
                // Determine the index of 
                // the larger child 
                var maxIndex = currentIndex 
                if leftChildIndex < heap.count && heap[leftChildIndex] > heap[maxIndex] { 
                    maxIndex = leftChildIndex 
                } 
                if rightChildIndex < heap.count && heap[rightChildIndex] > heap[maxIndex] { 
                    maxIndex = rightChildIndex 
                } 
                  
                // If the heap property is  
                // restored, break out of the loop 
                if maxIndex == currentIndex { 
                    break
                } 
                  
                // Otherwise, swap the current 
                // element with its larger child 
                heap.swapAt(currentIndex, maxIndex) 
                currentIndex = maxIndex 
            } 
        } 
          
        return topElement 
    } 
      
    // Get the top element of the 
    // heap without removing it 
    func peek() -> T? { 
        return heap.first 
    } 
      
    // Check if the heap is empty 
    var isEmpty: Bool { 
        return heap.isEmpty 
    } 
} 

Time complexity:

Insertion: O(log n)
Removal: O(log n)
Peek: O(1)

Auxiliary Space: O(n)

sahoopratyushkumar3

Improve

How to Implement Data Structures in Ruby?

Heap data structure implementation in swift

Types of Heap Data Structure:

Swift

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?