Heaps
A heap is a special type of binary tree that satisfies the heap property. In a heap, the parent node always follows a specific order relation with respect to its children. Heaps are commonly used in various algorithms, especially in sorting and priority queues, due to their efficient access to the minimum or maximum element.
There are two main types of heaps, based on the order property they follow:
- Max-heap: In a max-heap, each node’s value is greater than or equal to the values of its children, with the largest element positioned at the root. Max-heaps are commonly used in algorithms that need efficient access to the maximum element, such as heapsort and priority queue implementations. In max-heap, the heap property is as follows:
![<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mi>A</mi><mfenced open="[" close="]"><mi>i</mi></mfenced><mo>≥</mo><mi>A</mi><mfenced open="[" close="]"><mrow><mn>2</mn><mi>i</mi><mo>+</mo><mn>1</mn></mrow></mfenced></mrow></mrow></math>](https://static.packt-cdn.com/products/9781835886823/graphics/image/1917.png)
(left child)![<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mml:mi>A</mml:mi><mml:mfenced open="[" close="]" separators="|"><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:mfenced><mml:mo>≥</mml:mo><mml:mi>A</mml:mi><mml:mfenced open="[" close="]" separators="|"><mml:mrow><mml:mn>2</mml:mn><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:mfenced></mml:math>](https://static.packt-cdn.com/products/9781835886823/graphics/image/1918.png)
(right child), where 
is the array representation of the heap
- Min-heap: In a min-heap, the value of each node is less than or equal to the values of its children. The smallest element is always at the root. Min-heaps...
