The STL Vector class simplifies the heap implementation with various methods tha

Question

The STL Vector class simplifies the heap implementation with various methods that simplify adding data to the end of the vector and with its ability to automatically resize itself. If the Heap class used an array as the heap versus a vector, what additional things must be considered and implemented to allow the use of an array to build the heap? Heap sort is typically done in place on the same array that is used to store the tree. Rewrite the heap_sort method to have it perform the sorting on the heap vector. The return type of the method will be vector and the parameter list will be empty. This method does not have support different sort orders, however, using this approach results in the following ordering: max-heap: heap_sort results in an ascending ordered array min-heap: heap_sort results in an descending ordered array

Explanation / Answer

1.

STL provides almost all the methods required to implement Min or Max Heap.
For example, STL provides priority_queue, which is a Max heap. To use the priority_queue as min heap,
we need to tweak the comparator operator used by the library.

If we use Array instead of STL vector, then we have to implement all the methods required.
Starting from initializing the size of the Heap, we have to take care of everything.
The below methods need to be implemented is we are using the array.

MinHeap(int capacity);

// to heapify a subtree with root at given index
void MinHeapify(int );

int parent(int i) { return (i-1)/2; }

// Returns the minimum key (key at root) from min heap
int getMin() { return harr[0]; }

// Deletes a key stored at index i
void deleteKey(int i);

// Inserts a new key 'k'
void insertKey(int k);
  
   // to get index of left child of node at index i
int left(int i) { return (2*i + 1); }

// to get index of right child of node at index i
int right(int i) { return (2*i + 2); }

// to extract the root which is the minimum element
int extractMin();

// Decreases key value of key at index i to new_val
void decreaseKey(int i, int new_val);
  
The same holds good for Max Heap.

2. Please find the implementation below:

void Swap(std::vector<int>& vHeap, std::vector<int>::size_type i, std::vector<int>::size_type j)
{
if(i == j)
return;

int temp;
temp = vHeap[i];
vHeap[i] = vHeap[j];
vHeap[j] = temp;
}

void Sift(std::vector<int>& vHeap, const std::vector<int>::size_type heapSize, const std::vector<int>::size_type siftNode)
{
std::vector<int>::size_type i, j;

j = siftNode;
do
{
i = j;
if(((2*i + 1) < heapSize) && vHeap[j] < vHeap[2*i + 1])
j = 2*i + 1;
if(((2*i + 2) < heapSize) && vHeap[j] < vHeap[2*i + 2])
j = 2*i + 2;

Swap(vHeap, i, j);
}
while(i != j);
}

void MakeInitialHeap(std::vector<int>& vHeap)
{
for(int i = vHeap.size() - 1; i >= 0; --i)
{
Sift(vHeap, vHeap.size(), i);
}
}

void HeapSort(std::vector<int>& vHeap)
{
MakeInitialHeap(vHeap);
for(std::vector<int>::size_type i = vHeap.size()-1; i > 0; --i)
{
Swap(vHeap, i, 0);
Sift(vHeap, i, 0);
}
}

int main(int argc, char *argv[])
{
std::vector<int>::size_type size;
std::vector<int> vHeap;
std::cout<<"How many numbers to be sorted?";
std::cin>>size;

std::cout<<"Enter the numbers to be sorted:- ";

int value;
for(std::vector<int>::size_type i = 0; i < size; ++i)
{
std::cout<<"Enter number "<<i+1<<":";
std::cin>>value;
vHeap.push_back(value);
}

HeapSort(vHeap);
  
for(std::vector<int>::size_type i = 0; i < vHeap.size(); ++i)
{
std::cout<<vHeap[i]<<" ";
}
  
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.