Practice - 5 Tasks
Answer the questions below
1fill in blank
easyComplete the code to create a priority queue using a min-heap for Huffman nodes.
DSA Javascript
class PriorityQueue { constructor() { this.heap = []; } insert(node) { this.heap.push(node); this.[1](); } bubbleUp() { let index = this.heap.length - 1; while (index > 0) { let parentIndex = Math.floor((index - 1) / 2); if (this.heap[parentIndex].freq <= this.heap[index].freq) break; [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]]; index = parentIndex; } } }
Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Calling bubbleDown instead of bubbleUp after insertion.
✗ Incorrect
After inserting a node, we need to move it up to maintain the min-heap property, so we call bubbleUp().
2fill in blank
mediumComplete the code to remove and return the node with the smallest frequency from the priority queue.
DSA Javascript
extractMin() {
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.[1](0);
return min;
}
bubbleDown(index) {
const length = this.heap.length;
let smallest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < length && this.heap[left].freq < this.heap[smallest].freq) {
smallest = left;
}
if (right < length && this.heap[right].freq < this.heap[smallest].freq) {
smallest = right;
}
if (smallest !== index) {
[this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
this.bubbleDown(smallest);
}
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Calling bubbleUp instead of bubbleDown after removal.
✗ Incorrect
After replacing the root with the last element, we move it down to restore heap order using bubbleDown().
3fill in blank
hardFix the error in the code that builds the Huffman tree by combining two smallest nodes.
DSA Javascript
buildHuffmanTree(freqMap) {
const pq = new PriorityQueue();
for (const char in freqMap) {
pq.insert({ char, freq: freqMap[char], left: null, right: null });
}
while (pq.heap.length > 1) {
const left = pq.extractMin();
const right = pq.extractMin();
const merged = {
char: null,
freq: left.freq + right.freq,
left: left,
right: right
};
pq.[1](merged);
}
return pq.extractMin();
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using extractMin instead of insert to add the merged node.
✗ Incorrect
After merging two nodes, we must insert the new node back into the priority queue using insert().
4fill in blank
hardFill both blanks to generate Huffman codes by traversing the tree recursively.
DSA Javascript
generateCodes(node, code, codes) {
if (!node) return;
if (node.char !== null) {
codes[node.char] = code;
} else {
this.generateCodes(node.[1], code + '[2]', codes);
this.generateCodes(node.right, code + '1', codes);
}
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using 'right' or '1' for the left child traversal.
✗ Incorrect
We traverse left child adding '0' to the code, so blanks are 'left' and '0'.
5fill in blank
hardFill all three blanks to encode a string using the generated Huffman codes.
DSA Javascript
encode(input, codes) {
let result = '';
for (const [1] of input) {
result += codes[[2]];
}
return result;
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using different variable names in loop and codes indexing.
✗ Incorrect
We iterate over each character named 'character' and append codes[character] to result. The first blank is the loop variable, second is the same variable, third is the variable used in codes indexing.