A binary heap is a specific type of data structure that takes the form of a binary tree and is used to implement priority queues efficiently. It was introduced by J. W. J. Williams in 1964 primarily as a data structure for the heapsort sorting algorithm. Binary heaps can be categorized into two types: min-heaps and max-heaps, based on the ordering of the elements within them.
Characteristics of Binary Heap
Complete Binary Tree: A binary heap is a complete binary tree. This means that it is fully filled at all levels except possibly the last level, which is filled from left to right. This property ensures that the binary heap can be efficiently represented as an array[1][3][5][6][8][9][14].
Heap Property: In a binary heap, the key stored in each node is either greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) the keys in the node's children. This property must be recursively true for all nodes in the binary tree. In a max-heap, the maximum element is found at the root, while in a min-heap, the minimum element is located at the root[1][3][5][6][8][9][14].
Operations on Binary Heap
Binary heaps support several operations, which are crucial for their functionality in priority queues and sorting algorithms:
Insertion: Adding a new element to a binary heap involves placing the element at the end of the heap (to maintain the complete binary tree property) and then adjusting the heap to maintain the heap property. This adjustment is done through a process known as "heapify" or "percolate up," where the added element is compared and possibly swapped with its parent until the heap property is restored. This operation has a time complexity of $$O(\log n)$$[2][4][6][10][14][15].
Deletion: The standard deletion operation in a binary heap involves removing the root element. In a max-heap, this would be the maximum element, and in a min-heap, the minimum element. After removal, the last element in the heap is moved to the root, and the heap is adjusted (heapified) to maintain the heap property. This operation also has a time complexity of $$O(\log n)$$[2][4][6][10][14][15].
