# HEAP SORT PROGRAM

In this “HEAP SORT PROGRAM” covers Introduction, Largest heap element, HEAP IMPLEMENTATION USING ARRAY REPRESENTATION, REMOVING THE LARGEST ELEMENT FROM THE HEAP, INSERTING A NEW ELEMENT INTO THE HEAP, PRIORITY QUEUES, DEFINITION OF MAX HEAP, DEFINITION OF MIN HEAP, INSERTION, DELETION, HEAP SORT, HEAPIFY, BUILD HEAP, ALGORITHM, procedure, C program, Time Analysis, and ends with the COMPARISON WITH QUICK SORT, MERGE SORT AND HEAP SORT.

## INTRODUCTION OF HEAP SORT

In computer science, **heapsort** is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.

It’s worst-case performance, it takes O(n log n) and in best-case performance, it takes O(n log n) and average-case performance, it takes O(n log n). Space complexity is O(n).

The heapsort algorithm can be divided into two parts.

In the first step, a heap is built out of the data (see Binary heap § Building a heap). The heap is often placed in an array with the layout of a complete binary tree. The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the node’s parent, left child branch, or right child branch are simple expressions. For a zero-based array, the root node is stored at index 0; if `i`

is the index of the current node, then

1 2 3 |
iParent(i) = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer. iLeftChild(i) = 2*i + 1 iRightChild(i) = 2*i + 2 |

In the second step, a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap), and inserting it into the array. The heap is updated after each removal to maintain the heap property. Once all objects have been removed from the heap, the result is a sorted array.

It is a binary tree with the following properties:

Property 1: it is a complete binary tree

Property 2: the value stored at a node is greater or equal to the values stored at the children (heap property)

## LARGEST HEAP ELEMENT

From Property 2, the largest value of the heap is always stored at the root

## HEAP IMPLEMENTATION USING ARRAY REPRESENTATION

A heap is a complete binary tree, so it is easy to be implemented using an array representation.

20 | 14 | 17 | 8 | 6 | 9 | 4 | 1 |

## REMOVING THE LARGEST ELEMENT FROM THE HEAP

- Copy the bottom rightmost element to the root.
- Delete the bottom rightmost node
- Fix the heap property by calling ReheapDown

## INSERTING A NEW ELEMENT INTO THE HEAP

- Insert the new element in the next bottom leftmost place
- Fix the heap property by calling Reheapup

## PRIORITY QUEUES:

It is a queue with each element being associated with a “priority”

From the elements in the queue, the one with the highest priority is dequeued first

## DEFINITION OF MAX HEAP

- Store data in ascending order
- Has property of A[Parent(i)] >= A[i]

## MAX HEAP ARRAY IS:

20 | 17 | 14 | 9 | 8 | 6 | 4 | 1 |

## DEFINITION OF MIN HEAP:

- Store data in descending order
- Has property of A[Parent(i)] <= A[i]

## MIN HEAP ARRAY IS:

1 | 4 | 6 | 8 | 9 | 14 | 17 | 20 |

## INSERTION:

Algorithm

1. Add the new element to the next available position at the

lowest level

2. Restore the max-heap property if violated

- General strategy is percolate up (or bubble up):

if the parent of the element is smaller than the

element, then interchange the parent and child.

OR

Restore the min-heap property if violated

- General strategy is percolate up (or bubble up):

if the parent of the element is larger than the

element, then interchange the parent and child.

## DELETION:

DELETE MAX:

- Copy the last number to the root (overwrite the maximum element stored there).
- Restore the max heap property by percolate down

DELETE MIN:

- Copy the last number to the root (overwrite the minimum element stored there
- Restore the min heap property by percolate down.

## HEAP SORT

A sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap.

PROCEDURES ON HEAP

- HEAPIFY
- BUILD HEAP
- HEAP SORT

## HEAPIFY:

Heapify picks the largest child key and compare it to the parent

key. If parent key is larger than heapify quits, otherwise it swaps

the parent key with the largest child key. So that the parent is now

becomes larger than its children.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
Heapify(A, i) { l left(i) r right(i) if l <= heapsize[A] and A[l] > A[i] then largest l else largest i if r <= heapsize[A] and A[r] > A[largest] then largest r if largest != i then swap A[i] A[largest] Heapify(A, largest) } |

## BUILD HEAP

We can use the procedure ‘Heapify’ in a bottom-up fashion to

convert an array A[1 . . n] into a heap. Since the elements in the

subarray A[n/2 +1 . . n] are all leaves, the procedure BUILD_HEAP

goes through the remaining nodes of the tree and runs ‘Heapify’

on each one. The bottom-up order of processing node guarantees

that the subtree rooted at children are heap before ‘Heapify’ is run

at their parent.

1 2 3 4 5 6 |
Buildheap(A) { heapsize[A] length[A] for i |length[A]/2 //down to 1 do Heapify(A, i) } |

## HEAPSORT ALGORITHM:

The heap sort algorithm starts by using procedure BUILD-HEAP to

build a heap on the input array A[1 . . n]. Since the maximum

element of the array stored at the root A[1], it can be put into its

correct final position by exchanging it with A[n] (the last element in

A). If we now discard node n from the heap than the remaining

elements can be made into heap. Note that the new element at

the root may violate the heap property. All that is needed to

restore the heap property.

1 2 3 4 5 6 7 8 |
Heapsort(A) { Buildheap(A) for i length[A] //down to 2 do swap A[1] A[i] heapsize[A] heapsize[A] - 1 Heapify(A, 1) } |

The heap sort algorithm consists of two phrases:

- To sort the elements in the decreasing order, use a min heap
- To sort the elements in the increasing order, use a max heap

## Procedure:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
Heapsort(A as array) BuildMaxHeap(A) for i=n to 1 swap(A[1],A[i]) n=n-1 Heapify(A,1) BuildMaxHeap(A as array) n=elements_in(A) for i=floor(n/2) to 1 do Heapify(A,i) Heapify(A as array, i as int) left=2i right=2i+1 if(left <= n ) and (A[left]>A[i]) max=left else max=i if(right<=n) and (A[right]> A[max]) max=right if(max!=i) swap(A[i],A[max]) Heapify(A,max) |

## C PROGRAM:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<stdio.h> int temp; void heapify(int arr[], int size, int i) { int largest = i; int left = 2*i + 1; int right = 2*i + 2; if (left < size && arr[left] >arr[largest]) largest = left; if (right < size && arr[right] > arr[largest]) largest = right; if (largest != i) { temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, size, largest); } } void heapSort(int arr[], int size) { int i; for (i = size / 2 - 1; i >= 0; i--) heapify(arr, size, i); for (i=size-1; i>=0; i--) { temp = arr[0]; arr[0]= arr[i]; arr[i] = temp; heapify(arr, i, 0); } } void main() { int arr[100], n, i; printf("How many elements you are using?: "); scanf("%d",&n); printf("Enter %d elements: \n", n); for(i = 0; i < n; i++){ printf("Array[%d]: ",(1+i)); scanf("%d",&arr[i]); } heapSort(arr, n); printf("printing sorted elements\n"); for (i=0; i<n; ++i) printf("%d ",arr[i]); printf("\n "); } |

## INPUT-OUTPUT:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
How many elements you are using?: 10 Enter 10 elements: Array[1]: 3 Array[2]: 5 Array[3]: 7 Array[4]: 9 Array[5]: 2 Array[6]: 4 Array[7]: 6 Array[8]: 8 Array[9]: 1 Array[10]: 0 printing sorted elements 0 1 2 3 4 5 6 7 8 9 |

## TIME ANALYSIS:

- Build Heap Algorithm will run in O(n) time
- There are n-1 calls to Heapify each call requires O(log n) time
- Heap sort program combine Build Heap program and Heapify, Therefore it has the running time of O(n log n) time
- Total time complexity: O(n log n)

## COMPARISON WITH QUICK SORT, MERGE SORT AND HEAP SORT

- Quicksort is typically somewhat faster, due to better cache

behavior and other factors, but the worst-case running time for

quicksort is O (n 2 ), which is unacceptable for large data sets and

can be deliberately triggered given enough knowledge of the

implementation, creating a security risk. - The quicksort algorithm also requires Ω (log n) extra storage

space, making it not a strictly in-place algorithm. This typically does not pose a problem except on the smallest embedded systems, or on systems where memory allocation is highly restricted. Constant space (in-place) variants of quicksort are possible to construct but are rarely used in practice due to their extra complexity. - Thus, because of the O(n log n), upper bound on heap sort’s running time and constant upper bound on its auxiliary storage, embedded systems with real-time constraints or systems concerned with security often use heap sort.
- Heap sort also competes with merge sort, which has the same time bounds, but requires Ω(n) auxiliary space, whereas heap sort requires only a constant amount. Heap sort also typically runs more quickly in practice. However, merge sort is simpler to understand than heap sort, is a stable sort, parallelizes better, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network-attached storage. Heap sort shares none of these benefits; in particular, it relies strongly on random access.