Data Structure - Binary Heap

Introduction

Heap is a complete binary tree in which value of any node is less than or equal to the values of its children. This implies that the least element is always in the root of the tree.

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 to the left as possible.

• Heap can be implemented using an array.
• Heap can be used to implement Priority Queue
• Heap can be used to find the first N elements in ascending (descending) order in the set of elements
• Binary Heap can be used to implement the following algorithms: Heap Sort, Top N, Prim's Minimum Spanning tree.

Implementation

C# implementation - Open on Github

Algorithms that use binary heap:

• Top N
• Heap Sort
• Prim's Algorithm
• K-Way Merge Sort

Problems

Prim's algorithm is a very special algorithm for me. I have used it to solve one of the tasks during the All-Ukrainian School Olympiad in Informatics in 2001 and got the 3rd degree place. Which in turn helped me to enter the University of my choice.

• Prim's (MST) : Special Subtree

Links

• Jon Bentley, Programming Pearls, second edition, Column 14
• Wikipedia article about Heap
• Prim's algorithm
• Fibonacci Heap