cs301 Data Structure Assignmnet Solution

Question: Write simple algorithm for Heap Sort. Solution:     The heapsort algorithm uses the data structure called the heap. A heap is defined as a complete binary tree in which each node has a value greater than both its children (if any). Each node in the heap corresponds to an element of the array, with the root node corresponding to the element with index 0 in the array. Considering a node corresponding to index i, then its left child has index (2*i + 1) and its right child has index (2*i + 2). If any or both of these elements do not exist in the array, then the corresponding child node does not exist either. Note that in a heap the largest element is located at the root node. The code for the algorithm is:     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)     }     Buildheap(A){         heapsize[A] <- length[A]         for i <- |length[A]/2| downto 1             do Heapify(A, i)     }     Heapsort(A){         Buildheap(A)         for i <- length[A] downto 2             do swap A[1] <-> A[i]             heapsize[A] <- heapsize[A] - 1             Heapify(A, 1)     }