Read Algorithm 6A on page 258 (Given Above) ^^ A. Write a c++ program that uses
ID: 3776532 • Letter: R
Question
Read Algorithm 6A on page 258 (Given Above) ^^
A. Write a c++ program that uses the code given below (the code given below is just an outline for the method we are trying to implement) to implement finding the kth smallest element in a sequence of integers. (Using the algorithm described above in the screenshot)
B. Use this new program you derive in A to find the 5th smallest element in the sequence { 121, 81, 16, 100, 25, 0, 1, 9, 4, 36, 64, 49 }
Algorithm 6A For simplicity, we assume that we are interested in finding the hth smallest element. The algorithm is simple. We read the N elements into an array we then apply the buildHeap algorithm to this array Finally, we perform h deleteMin operations. The last element extracted from the heap is our answer. It should be clear that by changing the heap-order property, we could solve the original problem of finding the kth largest element. The correctness of the algorithm should be clear. The worst-case timing is O(N) to construct the heap, if buildHeap is used, and o log N) for each deleteMin. Since there are k deleteMins, we obtain a total running time of O N k log N). If k ON/log N), then the running time is dominated by the buildHeap operation and is O For larger values of k, the running time is oklog N). If k rN/21, then the running time is O(N log N) Notice that if we run this program for k N and record the values as they leave the heap, we will have essentially sorted the input file in o(N log N time. This idea can be refined to obtain a fast sorting algorithm known as heapsort.Explanation / Answer
A.) Please find below the .cpp program with the output for the algorithm shown above:
#include <iostream>
#include <vector>
using namespace std;
class UnderflowException
{
};
template<typename Comparable>
class BinaryHeap
{
public:
explicit BinaryHeap(int capacity = 100) :
array(capacity + 1), currentSize(0)
{
}
explicit BinaryHeap(const vector<Comparable> & items) :
array(items.size() + 10), currentSize(items.size())
{
for (unsigned i = 0; i < items.size(); i++)
array[i + 1] = items[i];
buildHeap();
}
bool isEmpty() const
{
return currentSize == 0;
}
/**
* To Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
const Comparable & findMin() const
{
if (isEmpty())
throw UnderflowException();
return array[1];
}
/**
* This will Insert item x, allowing duplicates.
*/
void insert(const Comparable & x)
{
if (currentSize == array.size() - 1)
array.resize(array.size() * 2);
// Percolate up
int hole = ++currentSize;
for (; hole > 1 && x < array[hole / 2]; hole /= 2)
array[hole] = array[hole / 2];
array[hole] = x;
}
/**
* This will remove the minimum item.
* Throws UnderflowException if empty.
*/
void deleteMin()
{
if (isEmpty())
throw UnderflowException();
array[1] = array[currentSize--];
percolateDown(1);
}
/**
* This will remove the minimum item and place it in minItem.
* Throws Underflow if empty.
*/
void deleteMin(Comparable & minItem)
{
if (isEmpty())
throw UnderflowException();
minItem = array[1];
array[1] = array[currentSize--];
percolateDown(1);
}
void makeEmpty()
{
currentSize = 0;
}
void printHeap()
{
cout << "Start of heap" << endl;
for (unsigned i = 1; i <= currentSize; i++)
cout << array[i] << endl;
cout << "End of heap" << endl;
}
void prettyPrintHeap()
{
if(isEmpty())
{
cout << "The heap is empty." << endl;
return;
}
unsigned index = 1, levelSize = 1;
while (index <= currentSize)
{
for (unsigned i = 0; i < levelSize; i++)
{
if (index + i > currentSize)
break;
cout << array[index + i] << " ";
}
cout << endl;
index += levelSize;
levelSize *= 2;
}
}
private:
vector<Comparable> array; // The heap array
unsigned currentSize; // Number of elements in heap
/**
* To establish heap order property from an arbitrary
* arrangement of items. This runs in linear time.
*/
void buildHeap()
{
for (int i = currentSize / 2; i > 0; i--)
percolateDown(i);
}
/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
void percolateDown(unsigned hole)
{
unsigned child;
Comparable tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child)
{
child = hole * 2;
if (child != currentSize && array[child + 1] < array[child])
child++;
if (array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
};
int main()
{
BinaryHeap<int> h(15);
h.makeEmpty();
h.insert(10);
h.insert(12);
h.insert(1);
h.insert(14);
h.insert(6);
h.insert(5);
h.insert(8);
h.insert(15);
h.insert(3);
h.insert(9);
h.insert(7);
h.insert(4);
h.insert(11);
h.insert(13);
h.insert(2);
cout << "Original Heap." << endl;
h.printHeap();
cout << endl;
h.prettyPrintHeap();
cout << endl;
cout << "After first deleteMin." << endl;
h.deleteMin();
h.printHeap();
cout << endl;
h.prettyPrintHeap();
cout << endl;
cout << "After second deleteMin." << endl;
h.deleteMin();
h.printHeap();
cout << endl;
h.prettyPrintHeap();
cout << endl;
cout << "After third deleteMin." << endl;
h.deleteMin();
h.printHeap();
cout << endl;
h.prettyPrintHeap();
cout << endl;
return 0;
}
Output :-
Original Heap.
Start of heap
1
3
2
6
7
5
4
15
14
12
9
10
11
13
8
End of heap
1
3 2
6 7 5 4
15 14 12 9 10 11 13 8
After first deleteMin.
Start of heap
2
3
4
6
7
5
8
15
14
12
9
10
11
13
End of heap
2
3 4
6 7 5 8
15 14 12 9 10 11 13
After second deleteMin.
Start of heap
3
6
4
13
7
5
8
15
14
12
9
10
11
End of heap
3
6 4
13 7 5 8
15 14 12 9 10 11
After third deleteMin.
Start of heap
4
6
5
13
7
10
8
15
14
12
9
11
End of heap
4
6 5
13 7 10 8
15 14 12 9 11
B.) Insert { 121, 81, 16, 100, 25, 0, 1, 9, 4, 36, 64, 49 } into the above program and it will get you the 5th smallest element.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.