C Program: Implementing Heap sort with max Heap
4. Heap Sort Extended Challenges
Write a C program that uses the max heap data structure to implement heap sort. Show the sorting process on an array of integers.
Sample Solution:
C Code:
Output:
Original Array: 14 10 0 9 15 5 7 Sorted Array: 0 5 7 9 10 14 15
Explanation:
In the exercise above,
- maxHeapify: This function takes an array, its size, and an index as input and ensures that the subtree rooted at that index maintains the max-heap property. It recursively swaps elements to ensure the largest element is at the root.
- heapSort: This function performs heap sort on an array. It first builds a max heap from the array, then repeatedly extracts the maximum element (root) and calls maxHeapify on the reduced heap.
- printArray: This function prints the elements of an array.
- In the main function,
- It initializes an array.
- Prints the original array.
- Calls heapSort to sort the array.
- Prints the sorted array.
Flowchart:
For more Practice: Solve these Related Problems:
- Write a C program to implement heap sort using a max heap and optimize the algorithm by reducing unnecessary swaps.
- Write a C program to visualize the heap sort process by printing the heap after each swap operation.
- Write a C program to perform heap sort on an array of structures sorted by a key field using a max heap.
- Write a C program to implement heap sort using an iterative heapify approach and compare its performance with the recursive method.
C Programming Code Editor:
Previous: Construct Min Heap from random and sorted arrays.
Next: Implementing and testing Heapify function.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.