In this course, we will learn how to implement an Absolute Value Heap in JavaScript. An Absolute Value Heap is a heap structure sorted by two criteria, primarily arranging the data based on absolute values. For instance, if the absolute values are the same, the actual values are sorted accordingly.
Problem Description
We will solve an algorithm problem by constructing an Absolute Value Heap and performing the given tasks. The problem is as follows.
Given an array of integers, perform the operation of deleting and returning the number with the smallest absolute value using the Absolute Value Heap. In cases where the absolute values are the same, the smaller actual value is deleted first.
Input Format
["I 5", "I -5", "I 3", "I -2", "I 0", "I 4", "D 1", "D 1"]
Output Format
[0, -2, 3, 4]
Problem Solving Process
To implement an Absolute Value Heap, we can use JavaScript arrays. We declare an array and implement methods for insertion and deletion based on this array.
Step 1: Define the Heap Class
First, we will design the basic structure of the heap. The heap must always maintain a specific relationship between parent nodes and child nodes according to certain rules. It is sorted in order of increasing absolute value, and in cases of equal absolute values, it is sorted in order of the original values.
class AbsoluteValueHeap {
constructor() {
this.heap = [];
}
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
const element = this.heap[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.heap[parentIndex];
if (this.isCorrectOrder(element, parent)) break;
this.heap[index] = parent;
index = parentIndex;
}
this.heap[index] = element;
}
isCorrectOrder(child, parent) {
if (Math.abs(child) < Math.abs(parent)) return true;
if (Math.abs(child) > Math.abs(parent)) return false;
return child < parent;
}
delete() {
if (this.heap.length === 0) return null;
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.bubbleDown(0);
}
return min;
}
bubbleDown(index) {
const element = this.heap[index];
const length = this.heap.length;
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (!this.isCorrectOrder(element, leftChild)) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && !this.isCorrectOrder(element, rightChild)) ||
(swap !== null && !this.isCorrectOrder(leftChild, rightChild))
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
index = swap;
}
this.heap[index] = element;
}
peek() {
return this.heap[0] || null;
}
}
Step 2: Create a Function to Handle Commands
Now, we will create a function to process various commands based on the Absolute Value Heap. The command 'I' represents insertion, while 'D' represents deletion.
function processCommands(commands) {
const heap = new AbsoluteValueHeap();
const results = [];
for (const command of commands) {
const [action, value] = command.split(' ');
const num = parseInt(value);
if (action === 'I') {
heap.insert(num);
} else if (action === 'D' && num === 1) {
const deleted = heap.delete();
results.push(deleted !== null ? deleted : 0);
} else if (action === 'D' && num === -1) {
// No need to delete since it's implemented as a min heap
const deleted = heap.delete();
results.push(deleted !== null ? deleted : 0);
}
}
return results;
}
Step 3: Summary of the Complete Code
Now we will combine all the previously created code into a complete summary.
class AbsoluteValueHeap {
// Utilize the previously defined code.
}
function processCommands(commands) {
// Utilize the previously defined code.
}
// Execute the test example
const commands = ["I 5", "I -5", "I 3", "I -2", "I 0", "I 4", "D 1", "D 1"];
console.log(processCommands(commands)); // [0, -2, 3, 4]
Conclusion
In this course, we explored the process of implementing an Absolute Value Heap in JavaScript to solve the given problem. To aid understanding of the algorithm, we explained the basic concepts of heap sorting and the operational principles of a heap based on absolute values. We hope that this course will help you develop your skills in more advanced data structures and algorithm problem-solving.