C++ Coding Test Course, Implementing Absolute Value Heap

In this lecture, we will address an algorithm problem that involves implementing an absolute value heap. This problem is one of the frequently asked types in C++ programming and can be solved using a priority queue. An absolute value heap is a data structure that sorts based on the absolute value of a specific number.

Problem Description

An absolute value heap supports the following operations:

• Insert an integer x into the heap.
• Remove and return the integer with the smallest absolute value from the heap. If there are multiple numbers with the same absolute value, the smaller value is returned. If the heap is empty, return 0.

Input

The first line contains the number of operations N (1 ≤ N ≤ 100,000). The next N lines contain the operations to be performed. The operations are divided into two types:

• Insert: 0 x (−10⁹ ≤ x ≤ 10⁹) format, which inserts x into the absolute value heap.
• Delete: specified with 0, removes and returns the integer with the smallest absolute value from the absolute value heap.

Output

Print the results of the delete operations, one per line.

Example Input

10
1
-1
0
1
0
-1
0
0
0
0

Example Output

-1
1
0
0
0

Approach to the Problem

To solve this problem, we will use a priority queue. The C++ standard library provides std::priority_queue, which operates as a max heap by default. However, we need to create a min heap based on absolute values. Therefore, we will customize std::priority_queue to implement this.

Heap Implementation

To implement the absolute value heap, we will define the following comparison function:

struct Compare {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b)) {
            return a > b; // Choose the smaller value if the absolute values are the same
        }
        return abs(a) > abs(b); // Choose based on absolute value
    }
};

Based on the above comparison function, we can define the priority queue and perform insert and delete operations.

C++ Code Implementation

#include 
#include 
#include 
#include 

using namespace std;

// Define comparison operator
struct Compare {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b)) {
            return a > b; // Choose the smaller value if the absolute values are the same
        }
        return abs(a) > abs(b); // Choose based on absolute value
    }
};

int main() {
    int N;
    cin >> N;

    priority_queue, Compare> pq; // Customized priority queue
    
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            // Delete operation
            if (pq.empty()) {
                cout << 0 << endl; // Print 0 if empty
            } else {
                cout << pq.top() << endl; // Print the smallest value from the absolute value heap
                pq.pop(); // Delete from the heap
            }
        } else {
            // Insert operation
            pq.push(x); // Add value to the heap
        }
    }

    return 0;
}

Code Explanation

The above C++ code implements the absolute value heap:

• It uses the Compare structure to set the priority within the priority_queue.
• Within the main function, it reads input, deletes data from the heap when receiving 0, and inserts other numbers into the heap.

Time Complexity Analysis

The time complexity of this algorithm is as follows:

• Insert operation: O(log N)
• Delete operation: O(log N)

Therefore, for N operations, the overall time complexity is O(N log N).

Conclusion

In this lecture, we learned how to implement an absolute value heap in C++, and how to efficiently manage data using a priority queue. This problem is one of the important concepts in coding tests, so I hope you will deepen your understanding through practice.