Category Archives: Heaps

Binary Heaps: Introduction

Binary Heaps: Introduction A binary heap is a complete binary tree that satisfies the heap property. A heap can be classified further as either a max heap or a min heap. In a max heap, the keys of i.e. values held by parent nodes are always greater than or equal to those of the children and… Read More »

Why use Heaps over BST to implement priority queue?

Why choose heaps over BST to implement priority queue? A Priority Queue requires following operations to be efficient: Get minimum or maximum Insert an element Remove top priority element Decrease Key A Binary Heap supports above operations with time complexities as follows: getMin() or get Max(): O(1) insert(): O(Logn) extractMin() or extractMax(): O(Logn) decreaseKey(): O(Logn) Self Balancing… Read More »