A Binary Heap is a kind of binary tree that is a complete binary tree. A complete binary tree is the binary tree that all levels are fully filled withe exception of the last.

A Binary Heap can be a Min Heap or a Max Heap. For the Min Heap the root of the tree keeps the minimum value and for the Max Heap the root keeps the maximum value. And that is the strong part of the binary heap. The ability to get the min/max value of a set of numbers in O(1).

The representation of the Binary Heap is achieved with the help of an array. The first item of the array (index 0) keeps the root value (min or max). Each of the items can have a parent or left/right child. The parent of an item can be found by the next formula

(index - 1) // 2
                                        

The left and right child can be found by the following formulas:

left_child = index * 2 + 1
right_child = index * 2 + 2
                                        

The Binary Heap has 3 main operations. The Insertion where you insert a new value in the binary tree that must be placed in the correct spot (heapify up, you go from the last item of the array to the top in order to place the new value in the correct spot), extraction where you get the min/max value and extracted from the binary heap (heapify down, you go from index 0 to the bottom and swapping the values in the correct place) and peek min/max where you just get back the root element without any extraction.

The practical use of a binary heap is priority queues where you need to find the next job that must be executed in a given schedule with specified priorities.

Example In Python

class MinHeap:
    def __init__(self):
        self.heap = []

    def _parent(self, index):
        return (index - 1) // 2

    def _leftChild(self, index):
        return 2 * index + 1

    def _rightChild(self, index):
        return 2 * index + 2

    def _swap(self, index_1, index_2):
        tmp = self.heap[index_1]
        self.heap[index_1] = self.heap[index_2]
        self.heap[index_2] = tmp

    def _heapify_up(self, index):
        parent = self._parent(index)
        while parent >= 0:
            if self.heap[parent] > self.heap[index]:
                self._swap(parent, index)
            index = parent
            parent = self._parent(index)

    def _heapify_down(self, index):
        size = len(self.heap)
        while self._leftChild(index) < size:
            left = self._leftChild(index)
            right = self._rightChild(index)
            smaller = left

            if right < size and self.heap[right] < self.heap[smaller]:
                smaller = right

            if self.heap[smaller] > self.heap[index]:
                self._swap(smaller, index)
            index = smaller

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap)-1)

    def extract_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop(0)

        out = self.heap.pop(0)
        self._heapify_down(0)
        return out

    def __str__(self):
        return str(self.heap)


h = MinHeap()
h.insert(10)
h.insert(4)
h.insert(15)
h.insert(20)
h.insert(0)
h.insert(8)

print("Heap:", h)

print("Extract min:", h.extract_min())
print("Heap after extract:", h)
#
print("Extract min:", h.extract_min())
print("Heap after extract:", h)