Java Coding Test Course, Implementing Absolute Value Heap

One of the common problems encountered in coding tests is the implementation of data structures that efficiently store and manage data. In this article, we will explain a data structure called absolute value heap (absmin heap) and explore how to implement it using Java. The absolute value heap prioritizes based on the absolute value of the input data.

Problem Description

This problem involves implementing an absolute value heap for a given list of integers. The absolute value heap should support the following functionalities:

• Remove and return the smallest absolute value.
• Add the given integer to the absolute value heap.

The functioning of the implemented absolute value heap is as follows:

• Elements are sorted in ascending order of their absolute values.
• If absolute values are the same, the original smaller value is prioritized.

Input/Output Format

The input is provided in the following format:

    N
    operation[0]
    operation[1]
    ...
    operation[N-1]
    

Here, N is the number of operations, and each operation[i] is as follows:

• 0: Remove and print the smallest value from the absolute value heap.
• Other integer x: Add x to the absolute value heap.

Example

Input

    7
    5
    3
    6
    0
    -2
    4
    0
    

Output

    -2
    3
    

In the above example, the following process occurs:

• Adding 5, 3, and 6 stores [5, 3, 6] in the heap.
• When 0 is input, the smallest absolute value, -2, is returned.
• Additionally, the smallest absolute value of 3 is printed.

Implementation of Absolute Value Heap

Now, let’s implement the absolute value heap in Java. Essentially, Java allows us to implement heaps using PriorityQueue. However, in this case, we need to set the priority based on absolute values, so we will create a Comparator as follows.

Step 1: Define Heap Node

We create a data structure to store in the heap, where we will save each number’s original value and absolute value.

    class AbsHeapNode {
        int value;

        public AbsHeapNode(int value) {
            this.value = value;
        }

        public int getAbs() {
            return Math.abs(value);
        }
    }
    

Step 2: Define Comparator

We define a Comparator that can compare based on absolute values.

    class AbsMinComparator implements Comparator<AbsHeapNode> {
        @Override
        public int compare(AbsHeapNode a, AbsHeapNode b) {
            if (a.getAbs() != b.getAbs()) {
                return Integer.compare(a.getAbs(), b.getAbs());
            }
            return Integer.compare(a.value, b.value);
        }
    }
    

Step 3: Implement Absolute Value Heap

Now, we create a class that implements the actual absolute value heap.

    import java.util.PriorityQueue;

    public class AbsHeap {
        private PriorityQueue<AbsHeapNode> heap;

        public AbsHeap() {
            heap = new PriorityQueue<>(new AbsMinComparator());
        }

        public void insert(int value) {
            heap.offer(new AbsHeapNode(value));
        }

        public Integer removeMin() {
            AbsHeapNode node = heap.poll();
            return (node != null) ? node.value : null;
        }
    }
    

Step 4: Implement Main Method

Using the previously implemented classes, we write the main method.

    import java.util.Scanner;

    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            AbsHeap absHeap = new AbsHeap();
            int N = scanner.nextInt();

            for (int i = 0; i < N; i++) {
                int operation = scanner.nextInt();
                if (operation == 0) {
                    Integer minValue = absHeap.removeMin();
                    System.out.println(minValue != null ? minValue : 0);
                } else {
                    absHeap.insert(operation);
                }
            }

            scanner.close();
        }
    }
    

Conclusion

In the process of implementing the absolute value heap, it is crucial to define a suitable Comparator. This allows us to build an efficient data structure capable of solving the given problem. Problems like this often appear in coding tests as similar algorithm questions, so it is important to practice sufficiently to master them. Keep practicing various algorithms and data structures to become a better programmer. Thank you!