Kotlin is a programming language that has recently gained popularity among many developers due to its modern and concise syntax as well as its powerful features. In coding tests, specifically algorithm problem-solving, Kotlin demonstrates its usefulness as well. In this post, I would like to explain in detail how to implement an Absolute Value Heap using Kotlin.
Problem Description
The definition of an absolute value heap is as follows:
An absolute value heap is a priority queue that always places the smallest absolute value at the top.
If there are multiple values with the same absolute value, the actual smaller value is prioritized.
The operations of the heap are as follows:
- INSERT X: Adds integer X (to the priority queue)
- EXTRACT: Deletes and outputs the integer with the smallest absolute value
Input Format
The program’s input is provided over multiple lines, each containing a command.
Each line is given in the form of ‘INSERT X’ or ‘EXTRACT’.
Output Format
Each time an ‘EXTRACT’ command is called, the outputted value is printed on a new line.
Example
INPUT:
INSERT -5
INSERT 3
INSERT -1
EXTRACT
EXTRACT
INSERT -2
EXTRACT
EXTRACT
EXTRACT
OUTPUT:
-1
-2
3
Problem Analysis
To solve the given problem, we need to consider the following:
- How should we structure the priority queue?
- Should we utilize Java’s heap structure or Kotlin’s collections?
- How do we sort based on absolute values?
To create an absolute value heap, we can use a min-heap structure.
In Java, we can easily implement this using PriorityQueue.
We can also utilize this in Kotlin, and we can implement the desired functionality using a basic heap structure.
Implementation Process
1. Define Data Structure
The most crucial aspect of the absolute value heap is how we store the data.
Since we need to sort based on absolute values, we will use PriorityQueue to add and remove elements.
When adding elements, it is advisable to set both the absolute value and the original value.
2. Define Comparator
To define priorities in the PriorityQueue, we define a custom sorting rule (Comparator).
Here, values with smaller absolute values should come first, and in the case of equal absolute values, the actual smaller value should be prioritized.
val comparator = Comparator> { a, b ->
if (Math.abs(a.first) == Math.abs(b.first)) {
a.first.compareTo(b.first)
} else {
Math.abs(a.first).compareTo(Math.abs(b.first))
}
}
3. Process Commands
To handle the input commands, we run a loop.
If the command is INSERT X, we add the value to the heap, and if the command is EXTRACT, we remove the value from the heap and output it.
val priorityQueue = PriorityQueue>(comparator)
val reader = BufferedReader(InputStreamReader(System.`in`))
val n = reader.readLine().toInt()
repeat(n) {
val command = reader.readLine().split(" ")
when (command[0]) {
"INSERT" -> {
val value = command[1].toInt()
priorityQueue.add(Pair(value, value))
}
"EXTRACT" -> {
if (priorityQueue.isNotEmpty()) {
println(priorityQueue.poll().first)
} else {
println(0)
}
}
}
}
Full Code
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.PriorityQueue
fun main() {
val comparator = Comparator> { a, b ->
if (Math.abs(a.first) == Math.abs(b.first)) {
a.first.compareTo(b.first)
} else {
Math.abs(a.first).compareTo(Math.abs(b.first))
}
}
val priorityQueue = PriorityQueue>(comparator)
val reader = BufferedReader(InputStreamReader(System.`in`))
val n = reader.readLine().toInt()
repeat(n) {
val command = reader.readLine().split(" ")
when (command[0]) {
"INSERT" -> {
val value = command[1].toInt()
priorityQueue.add(Pair(value, value))
}
"EXTRACT" -> {
if (priorityQueue.isNotEmpty()) {
println(priorityQueue.poll().first)
} else {
println(0)
}
}
}
}
}
Conclusion
Implementing an absolute value heap is an essential part of dynamic data structures, and it can assist in solving various problems.
Through this tutorial, we learned how to implement a heap simply and effectively in Kotlin.
I hope you were able to realize how important it is to understand the essence of a problem and choose an efficient data structure while solving algorithm problems.
I look forward to improving our skills by tackling various algorithm problems together in the future!