Tasks: 1. Design two algorithms in pseudocode: one for the insert operation and
ID: 3727346 • Letter: T
Question
Tasks: 1. Design two algorithms in pseudocode: one for the insert operation and the other for the removeMin operation, both for a Heap implemented on an array H. 2. Using your favorite programming language, implement the Heap ADT on an array, in the following operations: insert, removeMin, min, size and isEmpty. Use the insert and removeMin algorithms of #1 3, Design the Heap-Sort algorithmn in pseudocode, which uses the Heap ADT of #2. Your algorithm should sort an array of integers in increasing order designed in #3. O-notatio favorite programming language, implement the Heap-Sort algorithm you 5. What are the worst and best-case time complexities of Insert, removeMin, and Heap-Sort, in n? Why? Your answer must be based on the algorithms you implemented. 6. Generate an array A of n random integers. Sort array A using Insertion-Sort, Quicksort, and Heap-Sort. Do this for arrays of size n 10, 100, 1000, 10000, 100000, 100000. Keep track of the CPU time each algorithm takes to sort these arrays. Comment on the running times you obtained, and compare them to the complexities as discussed in class. Hint: place the CPU times you obtained in a table.Explanation / Answer
1.Insert
first insert the element at the last index location of array then apply following algo:
heapInsert(int a[],int i){
while(i>1 and a[i/2]>a[i]){
swap(a[i],a[i/2]);
i=i/2;
}
}
i is the index of last element inserted.
O(logn)
2.Remove Min
replace the first element which is minimum with the last one and the make heap again for the first element.Note that the left and right child are already in heap.If child nodes are in heap and node itself is not then we can call minHeapify() for this node.Defination of minHeapify() is also given below.
heapRemoveMin(int a[]){
if(heap_size<1)
underflow
else{
min=a[1]
a[1]=a[heap_size]
heap_size=heap_size-1
min_heapify(a,1)
return min
}
}
minHeapify(int a[],int i){
l=2i;
r=2i+1;
if(l<=heap_size and a[i]>a[l])
smallest=l;
else
smallest=i;
if(r<=heap_size and a[i]>a[r])
smallest=r;
if(smallest!=i){
swap(a[i] and a[smallest])
minHeapify(a,smallest)
}
else
return
}
O(logn)
3.Minimum
Minimum is simply the first element.Just check if size is at least 1 then return the first element.
returnMin(int a[]){
if(heap_size<1)
"heap is empty"
else
return a[1]
}
4.Size
we can store size of heap in global veriable and use the value whenever required.
5.isEmpty
Similarly here also we can use the heap_size varible to check wheather heap is empty or not.
6.Heap sort
if the array is not a heap then first we have to build heap than simply call for removeMin() iteratively.
buildMinHeap(int a[]){
for(i=heap_size/2 down to 1){
minHeapify(a,i);
}
}
heapSort(int a[]){
buildMinHeap(a) //O(n)
for(i=heap_size down to 1){ // n times
b[i]=removeMin(); // O(logn)
}
}
complexity of Heap sort is O(nlogn).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.