Where Binary Heap is Used
A full binary tree (sometimes referred to as a proper binary tree or plane binary tree) is a tree in which every node other than the leaves has two children. In other words, each node has either 0 child or 2 children.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
A perfect binary tree is a binary tree with all leaf nodes at the same depth. All internal nodes have degree 2.
A Binary Heap is a binary tree with following 2 properties:
A very efficient way to implement a max heap is by using an array. To find an object’s children within the array we can use the formula:
leftChild = 2 * nodeIndex + 1
rightChild = 2 * nodeIndex + 2
To build a Heap it takes O(n):
There are 4 major methods for implementing a max heap:
When objects are first added to the heap they are initially added to the end of the heap (end of array).
Remove and return its largest object. The remove() method removes the root object (or first object in the array), immediately replaced with the last object in the heap, followed by siftDown()
The siftUp() method is used to move a newly inserted object from the last position in the array to its final location.
The siftDown() method is used to move the newly added root object (or first object in the array) to its correct position.
Binary Heap vs. Binary Search Tree
By comparison, if a binary tree is sorted, items to the left of a particular node are smaller, items to the right are larger, then we call it Binary Search Tree. Binary Heap does not guarantees the order while Binary Search Tree does. A Balanced Binary Search Tree guarantees height of O(log n) for n items.
Binary Heap vs. Red-Black Tree
Red-Black tree is a self-balancing binary search tree done by coloring each node in the tree with either red or black and preserving a set of properties that guarantee that the deepest path in the tree is not longer than twice the shortest one, while Binary Heap is a complete tree that guarantees the tree is balanced.
Leave a Reply.