Can I implement a binary heap by only using a TreeNode inferface (has children, or left/right, or/and parent.. something like this)?
I want to not rely on using array or linked list.
If I don't use array or linked list, I have a trouble inserting the next element in the correct place & keep it a complete binary tree (all non-leaf nodes are full). Also have trouble taking out the root and re-heapifying.
One key observation is this:
The path from the root to the last leaf in a complete binary tree is represented by the binary representation of the size of the tree (number of nodes in the tree).
For instance, this tree has 9 nodes.
1
/ \
4 2
/ \ / \
6 5 3 7
/ \
9 8
9 in binary is 1001. Skipping the most significant "1", this can be read from left-to-right as 0, 0, 1 or "left-left-right". That describes indeed the path from root to the leaf node with value 8!
The same principle holds for when you need to find the insertion point for a new node. Then first increase the size, so this becomes 10 in the example. The binary representation is 1010. Skipping the first digit, this represents "left-right-left". The last direction ("left") gives information about the edge that must be added. And indeed, "left-right" leads us to the node with value 5, and a new node has to be inserted as left-child of that node!
To restore the heap property after an insertion, keep track of the path towards the newly inserted leaf (for example, when coming back out of a recursive function), and wind that path back, each time verifying the heap property, and swapping values when necessary.
Similarly, for an extraction of the root value: first find the node to delete (see above), delete that node and assign the deleted value to the root node. Then sift down the heap to restore the heap property.
Here is an implementation in plain JavaScript -- it should be easy to port this to any other language:
class Node {
constructor(value) {
this.value = value;
this.left = this.right = null;
}
swapValueWith(other) { // We don't swap nodes, just their values
let temp = this.value;
this.value = other.value;
other.value = temp;
}
}
class HeapTree {
constructor() {
this.root = null;
this.size = 0;
}
insert(value) {
this.size++;
if (this.root == null) {
this.root = new Node(value);
} else { // Use the binary representation of the size to find insertion point
this.insertRecursive(this.root, 1 << (Math.floor(Math.log2(this.size)) - 1), value);
}
}
insertRecursive(node, bit, value) {
let side = this.size & bit;
let child;
if (side > 0) {
if (bit == 1) node.right = new Node(value);
child = node.right;
} else {
if (bit == 1) node.left = new Node(value);
child = node.left;
}
if (bit > 1) this.insertRecursive(child, bit>>1, value)
if (node.value > child.value) node.swapValueWith(child); // sift up
}
extract() {
if (this.root == null) return; // Nothing to extract
let value = this.root.value; // The value to return
if (this.size == 1) {
this.root = null;
} else {
// Use the binary representation of the size to find last leaf -- to be deleted
this.root.value = this.deleteRecursive(this.root, 1 << (Math.floor(Math.log2(this.size)) - 1));
// Sift down
let node = this.root;
while (true) {
let minNode = node;
if (node.left != null && node.left.value < minNode.value) minNode = node.left;
if (node.right != null && node.right.value < minNode.value) minNode = node.right;
if (minNode === node) break;
node.swapValueWith(minNode);
node = minNode;
}
}
this.size--;
return value;
}
deleteRecursive(node, bit) {
let side = this.size & bit;
let child;
if (side > 0) {
child = node.right;
if (bit == 1) node.right = null;
} else {
child = node.left;
if (bit == 1) node.left = null;
}
return bit == 1 ? child.value : this.deleteRecursive(child, bit>>1);
}
}
// Demo
let heap = new HeapTree();
for (let value of [4,2,5,8,7,9,0,3,1,6]){
heap.insert(value);
}
// Output the values in sorted order:
while (heap.root != null) {
console.log(heap.extract());
}