Finding kth smallest element using Max Heap

[darego]

I am trying to use a Max Heap in order to find the Kth smallest element. Although after hours of trying to get this to work I can't find a complete solution.

Max Heap: 203, 150, 15, 45, 4, 3, 1, 2, 5,
Currently some values work for k and some don't i.e. if I want to find the 2nd smallest element of the Max Heap it returns '150', which is correct.

But if I want to find the 7th smallest element, it prints out '5' instead of '1'

Can anyone see why?

  
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
using namespace std;

template<typename T>
class MaxHeap
{
private:
	vector<T> vec;
	int parentN(int);
	int leftN(int);
	int rightN(int);
	void trickleDownRec(int, int);
	void trickleUpRec(int);

public:
	void heapSort();
	void display();
	void insert(int);
	void remove();
	int kthSmallest(int k);
};


template<typename T>
int MaxHeap<T>::parentN(int i)
{
	return (i - 1) / 2;
}

template<typename T>
int MaxHeap<T>::leftN(int i)
{
	return (2 * i + 1);
}

template<typename T>
int MaxHeap<T>::rightN(int i)
{
	return (2 * i + 2);
}

template<typename T>
void MaxHeap<T>::trickleDownRec(int n, int i)
{

	// get left and right child of node at index i
	int left = leftN(i);
	int right = rightN(i);

	int largest = i;

	// compare vec[i] with its left and right child
	// and find largest value
	if (left < n && vec[left] > vec[i])
		largest = left;

	if (right < n && vec[right] > vec[largest])
		largest = right;

	// swap with child having greater value and 
	// call heapify-down on the child
	if (largest != i) {
		swap(vec[i], vec[largest]);
		trickleDownRec(n, largest);
	}
}

template<typename T>
void MaxHeap<T>::trickleUpRec(int i)
{
	// check if node at index i and its parent violates 
	// the heap property
	if (i && vec[parentN(i)] < vec[i])
	{
		// swap the two if heap property is violated
		swap(vec[i], vec[parentN(i)]);

		// call Heapify-up on the parent
		trickleUpRec(parentN(i));
	}
}


template<typename T>
void MaxHeap<T>::heapSort()
{
	int n = vec.size();
	for (int i = n - 1; i >= 0; i--) {
		swap(vec[0], vec[i]);
		trickleDownRec(i, 0);
	}
}

template<typename T>
void MaxHeap<T>::display()
{
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec.at(i) << ", ";
	}
}

template<typename T>
void MaxHeap<T>::insert(int key)
{
	// insert the new element to the end of the vector
	vec.push_back(key);

	// get element index and call heapify-up procedure
	int index = vec.size() - 1;
	trickleUpRec(index);
}

template<typename T>
void MaxHeap<T>::remove()
{
	vec[0] = vec.back();
	vec.pop_back();

	// call heapify-down on root node
	trickleDownRec(vec.size(), 0);

}

template<typename T>
int MaxHeap<T>::kthSmallest(int k)
{
	// Process remaining n-k elements.  If current element is 
	// smaller than root, replace root with current element 
	for (int i = 0; i < k; i++)
	{
		if (vec.at(i) < vec.at(0))
		{		
			MaxHeap<T>::remove();
			MaxHeap<T>::insert(vec.at(i));
		}		
	}
	// Return root 
	return vec.at(0);
}

int main()
{

	MaxHeap<int> pq;

	pq.insert(3);
	pq.insert(2);
	pq.insert(15);
	pq.insert(5);
	pq.insert(4);
	pq.insert(45);
	pq.insert(1);
	pq.insert(203);
	pq.insert(150);

	cout << "Max Heap: \n";
	pq.display();



	cout << "\n" << pq.kthSmallest(7);

	return 0;
}

[dhayden]

It seems to me that to remove the k'th smallest, you need to remove N-k items and then kth smallest is at the top of the heap.

To do that you have to add two simple methods to MaxHeap:

    T top() { return vec[0]; }
    size_t size() const { return vec.size(); }

Then kthSmallest() can be a standalone function, although it needs a MaxHeap as a paramenter. You could make it a member too if you wanted to avoid having to pass the heap as an argument.

template < typename T >
static T
kthSmallest(size_t k, MaxHeap<T> &heap)
{
    if (k > heap.size()) k = heap.size();
    for (size_t numToRemove = heap.size() - k; numToRemove; --numToRemove) {
        heap.remove();
    }
    return heap.top();
}

[darego]

edit: nvm that works perfect. thanks a lot! :)