Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Part 1: Implement the HeapSort algorithm. The HeapSort algorithm is simple: Build a heap and destroy it. For this, write another client program HeapDemo2.java reads

Part 1: Implement the HeapSort algorithm. The HeapSort algorithm is simple: Build a heap and destroy it. For this, write another client program HeapDemo2.java reads a text file with words, builds a heap with those words, and repeatedly removes the max item and puts it another text file. The resulting text file will have the words sorted in descending order. For example, if the input word file is:

there their about would these other which

the output word file is:

would which these there their other about

Test your program using a sample text file.

Heap.java

import java.util.ArrayList; public class Heap> { ArrayList heapList; public Heap() { heapList = new ArrayList(); } public int size() { return heapList.size(); } public boolean isEmpty() { return heapList.isEmpty(); } public void clear() { heapList.clear(); } public void enumerate() { System.out.println(heapList); } public void add(T item) { heapList.add(item); int index = heapList.size()-1; int pindex = (index-1)/2; T parent = heapList.get(pindex); while (index>0 && item.compareTo(parent)>0) { heapList.set(index, parent); heapList.set(pindex, item); index = pindex; pindex = (index-1)/2; parent = heapList.get(pindex); } } public T deleteMax() { if (isEmpty()) { System.out.println("Heap is empty"); return null; } else { T ret = heapList.get(0); //get the item in the root. This is the largest item. T item = heapList.remove(heapList.size()-1); //remove the last item. if (heapList.size()==0) return ret;//if there was only one item in the heap to begin with, we are done. heapList.set(0, item); //otherwise, proceed. Put the item in the root. int index, lIndex, rIndex, maxIndex; T maxChild; boolean found=false; index = 0; lIndex = index*2+1; rIndex = index*2+2; while (!found) { if (lIndex0) { maxChild = heapList.get(lIndex); maxIndex = lIndex; } else { maxChild = heapList.get(rIndex); maxIndex = rIndex; } //sift down if necesssary if (item.compareTo(maxChild)<0) { heapList.set(maxIndex, item); heapList.set(index, maxChild); index = maxIndex; } else found = true; } else if (lIndex < size()) //case 2: item to be sifted down has only left child //note: item to be sifted down cannot have only right child - it will violate the complete binary tree property { if (item.compareTo(heapList.get(lIndex))<0) { heapList.set(index, heapList.get(lIndex)); heapList.set(lIndex,item); index = lIndex; } else found = true; } else //case 3: item to be sifted down has no children found = true; lIndex = index*2+1; rIndex = index*2+2; } return ret; } } } 

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Modern Database Management

Authors: Jeffrey A. Hoffer Fred R. McFadden

4th Edition

0805360476, 978-0805360479

More Books

Students also viewed these Databases questions

Question

Types of physical Maps?

Answered: 1 week ago

Question

Explain Intermediate term financing in detail.

Answered: 1 week ago

Question

Types of cultural maps ?

Answered: 1 week ago

Question

Discuss the various types of leasing.

Answered: 1 week ago