Swift Coding Test Course, Implementing Absolute Value Heap

Problem Description

An absolute value heap is a data structure that follows these rules:

• The first element inserted is the one with the smallest absolute value.
• If the absolute values are the same, the smaller element value comes first.

Additionally, the operations that must be supported in the absolute value heap are as follows:

1. Insert a number into the heap.
2. Remove and return the number with the smallest absolute value from the heap.

The input consists of several commands, with each command being a form of inserting or removing a number. If the heap is empty, it outputs 0.

Input Format

The input is provided over multiple lines, and each line has the following format:

            1
            -1
            0
            1
            2 Ivy
            

Output Format

For each remove command, output the value at the top of the heap.

Problem Solving Process

To solve the problem, we will first define the structure of the absolute value heap and choose a data structure for it. A primary method to implement as a boilerplate is using an array-based heap structure. Here, we will utilize Swift’s basic data structure, Array.

Step 1: Designing the Heap Structure

To implement an absolute value heap, we need to define the structure and priority of the heap. We will prioritize the absolute value, and for elements with the same absolute value, we will base the priority on the actual number size. To do this, we will use a tuple that adopts the Comparable protocol.

Step 2: Implementing Insert Operation

When inserting into the heap, we add the new element to the end of the array and then move it up until the heap property is satisfied. This process is called ‘bubbling up’ or ‘up-heap’.

Step 3: Implementing Delete Operation

To delete the element with the smallest absolute value, we remove the root element, place the last element in the root position, and then move it down until the heap property is satisfied. This process is called ‘bubbling down’ or ‘down-heap’.

Swift Code Implementation

Now, let’s look at the actual Swift code based on the algorithm we have organized.

            import Foundation

            struct AbsoluteHeap {
                private var heap: [(value: Int, absolute: Int)] = []

                mutating func insert(_ value: Int) {
                    let absoluteValue = abs(value)
                    heap.append((value, absoluteValue))
                    upHeap(index: heap.count - 1)
                }

                mutating func pop() -> Int {
                    guard !heap.isEmpty else { return 0 }
                    let root = heap[0].value
                    heap[0] = heap.removeLast()
                    downHeap(index: 0)
                    return root
                }

                private mutating func upHeap(index: Int) {
                    var childIndex = index
                    let child = heap[childIndex]
                    var parentIndex = (childIndex - 1) / 2

                    while childIndex > 0 && (heap[parentIndex].absolute > child.absolute ||
                                              (heap[parentIndex].absolute == child.absolute && heap[parentIndex].value > child.value)) {
                        heap[childIndex] = heap[parentIndex]
                        childIndex = parentIndex
                        parentIndex = (childIndex - 1) / 2
                    }

                    heap[childIndex] = child
                }

                private mutating func downHeap(index: Int) {
                    var parentIndex = index
                    let count = heap.count

                    while true {
                        let leftChildIndex = 2 * parentIndex + 1
                        let rightChildIndex = 2 * parentIndex + 2
                        var candidateIndex = parentIndex

                        if leftChildIndex < count && (heap[leftChildIndex].absolute < heap[candidateIndex].absolute ||
                                                       (heap[leftChildIndex].absolute == heap[candidateIndex].absolute && heap[leftChildIndex].value < heap[candidateIndex].value)) {
                            candidateIndex = leftChildIndex
                        }
                        
                        if rightChildIndex < count && (heap[rightChildIndex].absolute < heap[candidateIndex].absolute ||
                                                        (heap[rightChildIndex].absolute == heap[candidateIndex].absolute && heap[rightChildIndex].value < heap[candidateIndex].value)) {
                            candidateIndex = rightChildIndex
                        }

                        if candidateIndex == parentIndex { break }
                        heap.swapAt(parentIndex, candidateIndex)
                        parentIndex = candidateIndex
                    }
                }
            }

            var absoluteHeap = AbsoluteHeap()
            let operations = [1, -1, 0, 1, 2]
            for op in operations {
                if op != 0 {
                    absoluteHeap.insert(op)
                } else {
                    print(absoluteHeap.pop())
                }
            }
            

Test Cases

Test Case 1

Input values used in the script: [1, -1, 0, 1, 2]

Expected output: 1 (when pop is performed)

Test Case 2

Additional input values used in the script: [2, -4, 0]

Expected output: -4 (when pop is performed)

Conclusion

We have now successfully implemented an absolute value heap using Swift. In this tutorial, we utilized the essence of algorithms, carefully chose data structures, and applied basic Swift syntax and structure to implement the heap's insertion and deletion processes. Through this implementation, I hope to solidify your prior knowledge of solving algorithm problems.

I look forward to solving various algorithm problems together in the future!