Heap sort as a priority queue

A heap is a specialized binary tree-based data structure that satisfies the heap property. It is often implemented as an array, where the elements of the heap are stored in a specific order to facilitate efficient operations such as insertion, deletion, and retrieval of the maximum (or minimum) element.

The heap property ensures that for any node i in the heap:

For a max-heap: The value of the parent node is greater than or equal to the values of its children nodes.

For a min-heap: The value of the parent node is less than or equal to the values of its children nodes.

The key properties of a heap are as follows:

Complete Binary Tree: A heap is a complete binary tree, meaning all levels of the tree are filled except possibly for the last level, which is filled from left to right.

Heap Order Property: The value of each node in a heap must satisfy the heap property, which depends on whether it's a max-heap or a min-heap.

Array Representation: A heap can be efficiently represented using an array, where the elements are stored in a manner that preserves the heap property. In such an array representation:

• The parent of the node at index i is at index i/2
• The left child of the node at index i is at index 2i
• The right child of the node at index i is at index 2i+1

Heaps are commonly used in priority queues, where elements with higher (or lower) priority are dequeued first. They are also used in algorithms such as heap sort and in various applications where efficient access to the maximum (or minimum) element is required.

In the diagram above, you can observe a particular sequence, i.e each node has greater value than any of its children.

Heap sort as a priority queue

A heap is a specialized binary tree-based data structure that satisfies the heap property. It is often implemented as an array, where the elements of the heap are stored in a specific order to facilitate efficient operations such as insertion, deletion, and retrieval of the maximum (or minimum) element.

The heap property ensures that for any node i in the heap:

For a max-heap: The value of the parent node is greater than or equal to the values of its children nodes.

For a min-heap: The value of the parent node is less than or equal to the values of its children nodes.

The key properties of a heap are as follows:

Complete Binary Tree: A heap is a complete binary tree, meaning all levels of the tree are filled except possibly for the last level, which is filled from left to right.

Heap Order Property: The value of each node in a heap must satisfy the heap property, which depends on whether it's a max-heap or a min-heap.

Array Representation: A heap can be efficiently represented using an array, where the elements are stored in a manner that preserves the heap property. In such an array representation:

• The parent of the node at index i is at index i/2
• The left child of the node at index i is at index 2i
• The right child of the node at index i is at index 2i+1

Heaps are commonly used in priority queues, where elements with higher (or lower) priority are dequeued first. They are also used in algorithms such as heap sort and in various applications where efficient access to the maximum (or minimum) element is required.

As you can see in the diagram below, we can use an array to store the nodes of the tree. Let’s say we have 7 elements with values {6, 4, 5, 3, 2, 0, 1}.

Note: An array can be used to simulate a tree in the following way. If we are storing one element at index i in array Ar, then its parent will be stored at index i/2 (unless its a root, as root has no parent) and can be access by Ar[ i/2 ], and its left child can be accessed by Ar[ 2 * i ] and its right child can be accessed by Ar[ 2 * i +1 ]. Index of root will be 1 in an array.

There are two types of Heap Data structure

Max Heap

A max heap is a specialized binary tree-based data structure where every parent node has a value greater than or equal to the values of its children nodes. In other words, the value of the root node is the maximum among all elements in the heap. Max heaps are often used to efficiently implement priority queues and heap sort algorithms.

key properties of a max heap:

Complete Binary Tree: A max heap is a complete binary tree, meaning all levels of the tree are filled except possibly for the last level, which is filled from left to right. This property ensures efficient use of space and enables the heap to be efficiently represented using an array.

Heap Order Property: In a max heap, for every node i (except for the root), the value of the parent node is greater than or equal to the values of its children nodes. Mathematically, this can be expressed as A[parent(i)]≥A[i],  where A[parent(i)] denotes the value of the parent node and  A[i] denotes the value of node i

Array Representation: Max heaps are commonly represented using arrays. The elements of the heap are stored in an array such that the parent node at index i is stored at index i, the left child of the node at index i is stored at index 2i,  and the right child of the node at index i is stored at index 2i+1. This array representation facilitates efficient access to elements and supports various heap operations.

Maximum Element: The maximum element in the max heap is located at the root of the tree (index 1 in the array representation). This property allows for constant-time retrieval of the maximum element.

Algorithm to convert HEAP into MAX HEAP [max_heapify operation]

void build_maxheap (int Arr[ ])
{
    for(int i = N/2 ; i >= 1 ; i-- )
    {
        max_heapify (Arr, i) ;
    }
}

Algorithm: max_heapify(Arr, i, N)

Input:
- Arr: an array representing the heap
- i: the index of the node to start heapifying from
- N: the size of the heap

Output:
- The array Arr with the max-heap property maintained starting from index i

1. Set left = 2*i  // Index of the left child
2. Set right = 2*i + 1  // Index of the right child
3. Set largest = i  // Index of the largest element among i, left, and right

4. If left ≤ N and Arr[left] > Arr[largest], then:
      Set largest = left

5. If right ≤ N and Arr[right] > Arr[largest], then:
      Set largest = right

6. If largest ≠ i, then:
      Swap Arr[i] with Arr[largest]
      Call max_heapify(Arr, largest, N) recursively

Find Max Heap for the given List of numbers: 1,4,3,7,8,9,10

Here N = 7, so starting from node having index N/2 = 3, (also having value 3 in the above diagram), we will call max_heapify from index N/2 to 1.

In step 1, in max_heapify(Arr, 3), as 10 is greater than 3, 3 and 10 are swapped and further call to max_heap(Arr, 7) will have no effect as 3 is a leaf node now.

In step 2, calling max_heapify(Arr, 2) , (node indexed with 2 has value 4) , 4 is swapped with 8 and further call to max_heap(Arr, 5) will have no effect, as 4 is a leaf node now.

In step 3, calling max_heapify(Arr, 1) , (node indexed with 1 has value 1 ), 1 is swapped with 10 .

Step 4 is a subpart of step 3, as after swapping 1 with 10, again a recursive call of max_heapify(Arr, 3) will be performed , and 1 will be swapped with 9. Now further call to max_heapify(Arr, 7) will have no effect, as 1 is a leaf node now.

In step 5, we finally get a max- heap and the elements in the array Arr will be :

MIN HEAP

A min heap is a specific type of binary heap where every parent node has a value smaller than or equal to the values of its children nodes. In other words, the smallest element is always stored at the root of the heap.

Properties of a Min Heap:

Heap Structure: A min heap is a complete binary tree where each level of the tree is fully filled except possibly for the last level, which is filled from left to right.

Parent-Child Relationship: In a min heap, the value of each parent node is less than or equal to the values of its children nodes. This property ensures that the minimum element is always at the root of the heap.

Indexing: The elements of the min heap are stored in an array, and the parent-child relationships are maintained through indexing. For any node at index i:

• Its left child is stored at index 2*i.
• Its right child is stored at index 2*i + 1.
• Its parent is stored at index i/2.

Minimum Element at Root: The root node of the min heap contains the minimum element in the entire heap.

Efficient Operations: Min heaps are efficient for operations such as finding the minimum element, extracting the minimum element, and inserting new elements while maintaining the min heap property.

Use in Priority Queues: Min heaps are commonly used to implement priority queues, where elements are dequeued in order of their priority (i.e., the smallest element is dequeued first).

Balanced Structure: Due to the complete binary tree structure, a min heap is relatively balanced, which ensures that the operations such as insertion and deletion have a time complexity of O(log n), where n is the number of elements in the heap.

A  min heap is a useful data structure for maintaining a collection of elements where efficient retrieval of the smallest element is required, such as in priority queue implementations and algorithms like Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm.

Algorithm to convert HEAP into MIN HEAP [min_heapify operation]

Algorithm min_heapify(Arr, i, N):
1. Set left = 2 * i
2. Set right = 2 * i + 1
3. Set smallest = i
4. If left ≤ N and Arr[left] < Arr[i], then set smallest = left
5. If right ≤ N and Arr[right] < Arr[smallest], then set smallest = right
6. If smallest ≠ i, then
    a. Swap Arr[i] with Arr[smallest]
    b. Call min_heapify(Arr, smallest, N)

Heap Sort

Following are the steps for heap sort

Build Max Heap: Initially, we build a max heap of elements in the array Arr.

Extract Maximum: The maximum element is stored at the root of the max heap, which is Arr[1]. We swap this element with the last element of the heap, and then remove it from the heap by reducing the heap size by one.

Re-Heapify: After extracting the maximum element, the heap may no longer satisfy the max heap property. So, we perform max_heapify on the root node (Arr[1]) to restore the max heap property.

Repeat: Steps 2 and 3 are repeated until all elements are in their correct sorted positions. This involves extracting the maximum element, re-heapifying the remaining elements, and reducing the heap size by one each time.

Sorted Array: After repeating the process until the heap size becomes 1, we will have all elements sorted in non-decreasing order.

Algorithm for Heap Sort

Algorithm heap_sort(Arr[0..N-1]):
    Input: Array Arr with N elements
    Output: Array Arr sorted in non-decreasing order

    1. Initialize heap_size to N.
    2. Build a max heap from the array Arr.
    3. Repeat for i from N to 2:
        a. Swap Arr[1] (root) with Arr[i].
        b. Decrement heap_size by 1.
        c. Call max_heapify(Arr, 1, heap_size) to restore the max heap property.
    4. The array Arr is now sorted in non-decreasing order.

Sort the given list of numbers using Heap Sort: 4, 3, 7, 1, 8, 5