Please show your work clearly and thank you in advance. 1) Build the heap tree, then apply the HEAPSORT algorithm to sort the array A = [9, 0, 8, 12, 11, 5, 4, 8, 1, 2, 7] in ascending order.(You must perform the HEAPSORT algorithm step-by-step) Your response is below but is not completed. Please draw the tree Definition: Heap sort is one of the sorting algorithms used to arrange a list of elements in order and used for a comparison-based sorting technique based on the binary heap data structure. The step-by-step information to applying the HEAPSORT algorithm to sort the given array A in ascending order: Explanation : Build the heap tree start by creating a binary tree representation of the input array A and each node is a value in A with the parent-child relationship. The root node is the first element of A, then left child of a node at index i in A is the node at index 2i+1, Later, right child of a node at index i in A is the node at index 2i+2. 12 11 5 4 / \ / 12 <= this tree must satisfy the heap property. Solution Perform the HEAPSORT algorithm to sort array A in ascending order. I will build a max heap from input array A then I will swap the root node. After the first swap, array A is [7, 0, 8, 12, 11, 5, 4, 8, 1, 2, 9] Here, I will perform a heapify operation on the root node to restore the heap property. After the first heapify operation, the array A is [8, 0, 5, 12, 11, 4, 2, 8, 1, 7, 9] I will repeat the steps until the entire array is sorted. After the second iteration, the array A is [8, 8, 5, 12, 11, 4, 2, 0, 1, 7, 9] third iteration [7, 8, 5, 12, 11, 4, 2, 0, 1, 8, 9] fourth iteration [5, 8, 4, 12, 11, 2, 1, 0, 7, 8, 9] fifth iteration [4, 8, 2, 12, 11, 1, 0, 5, 7, 8, 9] sixth iteration [2, 8, 1, 12, 11, 0, 4, 5, 7, 8]
Subj - Design
Please show your work clearly and thank you in advance.
1) Build the heap tree, then apply the HEAPSORT algorithm to sort the array A = [9, 0, 8, 12, 11, 5, 4, 8, 1, 2, 7] in ascending order.(You must perform the HEAPSORT algorithm step-by-step)
Your response is below but is not completed. Please draw the tree
Definition: Heap sort is one of the sorting algorithms used to arrange a list of elements in order and used for a comparison-based sorting technique based on the binary heap data structure.
The step-by-step information to applying the HEAPSORT algorithm to sort the given array A in ascending order:
Explanation :
- Build the heap tree start by creating a binary tree representation of the input array A and each node is a value in A with the parent-child relationship.
The root node is the first element of A, then left child of a node at index i in A is the node at index 2i+1, Later, right child of a node at index i in A is the node at index 2i+2.
12 11 5 4
/ \ /
- 12 <= this tree must satisfy the heap property.
Solution
- Perform the HEAPSORT algorithm to sort array A in ascending order. I will build a max heap from input array A then I will swap the root node. After the first swap,
array A is [7, 0, 8, 12, 11, 5, 4, 8, 1, 2, 9]
Here, I will perform a heapify operation on the root node to restore the heap property.
After the first heapify operation, the array A is [8, 0, 5, 12, 11, 4, 2, 8, 1, 7, 9]
I will repeat the steps until the entire array is sorted.
After the second iteration, the array A is [8, 8, 5, 12, 11, 4, 2, 0, 1, 7, 9]
third iteration [7, 8, 5, 12, 11, 4, 2, 0, 1, 8, 9]
fourth iteration [5, 8, 4, 12, 11, 2, 1, 0, 7, 8, 9]
fifth iteration [4, 8, 2, 12, 11, 1, 0, 5, 7, 8, 9]
sixth iteration [2, 8, 1, 12, 11, 0, 4, 5, 7, 8]
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images
