Extract minimum value from min heap

[clarkkent]

I am having trouble extracting the minimum value from a min heap, I am using vectors, for some reason the pop_back() function is not working...here is my code

heapsort.h

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

class minHeap
{
private:
	vector<int> items;

public:

	minHeap()
	{
	}

	int parent(int x )
	{
		return (x - 1) / 2; 
	}
	int lchild(int x)
	{
		return 2 * x + 1; 
	}
	int rchild(int x )
	{
		return 2 * x + 2; 
	}

	void insert(int x)
	{
		//step 1: put x at end heap
		items.push_back(x);

		//step 2: bubble-up
		bubbleUp(items.size() - 1);
	}

	int extractMin()
	{
		swap(items[0], items[items.size() - 1]);
		return items[items.size() - 1];
		items.pop_back(); //this is not working
		
		//bubbleDown(0); 

	}

	void bubbleDown(int x)
	{
		if (items[x] > items[lchild(x)])
		{
			swap(items[x], items[lchild(x)]);
			bubbleDown(lchild(x));
		}

	}

	void bubbleUp(int x)
	{
		if (items[x] < items[parent(x)])
		{
			swap(items[x], items[parent(x)]);
			bubbleUp(parent(x)); 
		}
	}

	void testDisplay()
	{
		for (int i = 0; i<items.size(); i++)
			cout << items[i] << endl;
	}
};

source.cpp

#include <iostream>
#include <string>
#include "heapsort.h"
using namespace std;


int main()
{
	////////////////////////////////////////////////
	//Step 1: Implement a basic min-heap priority queue
	////////////////////////////////////////////////

	minHeap pq;

	pq.insert(53);
	pq.insert(17);
	pq.insert(3);
	pq.insert(178);
	pq.insert(519);
	pq.insert(15);
	pq.insert(42);
	pq.insert(5);

	cout << "Extracting Minium: " << pq.extractMin() << endl; //3


	cout << endl;

	pq.testDisplay();
	

	
	return 0;
}

[Peter87]

The return statement ends the function so the pop_back function is never called.

[clarkkent]

Thank you!

[clarkkent]

Now the program is crashing, it says 'vector subscript out of range' the problem seems to be bubbleDown(0) inside the extractMin function, it does not crash when I comment it out.

[Peter87]

Vector subscript out of range means that you are trying to access elements in the vector that doesn't exist. In bubble up/down you should think about what happens if the item does not have a parent or a left or right child.

[ne555]

> Now the program is crashing
¿are we supposed to guess the modifications that you did?


> you should think about what happens if the item does not have a parent or a left or right child.
or if the item does not even exist.


> the problem seems to be
run through a debugger, let it crash, perform a backtrace.

[clarkkent]

Peter87 - how do I check if an item has a child? the only think I can think of is by checking if lchild(x) >= items.size() is this right?

ne555 how would I perform a backtrace?

[clarkkent]

this is my code so far

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

class minHeap
{
private:
	vector<int> items;

public:

	minHeap()
	{
	}

	int parent(int x )
	{
		return (x - 1) / 2; 
	}
	int lchild(int x)
	{
		return 2 * x + 1; 
	}
	int rchild(int x )
	{
		return 2 * x + 2; 
	}

	void insert(int x)
	{
		//step 1: put x at end heap
		items.push_back(x);

		//step 2: bubble-up
		bubbleUp(items.size() - 1);
	}

	bool isEmpty()
	{
		if (items.size() == 0)
		{
			return true;
		}
		else
			return false; 
	}

	int extractMin()
	{
	
		if (isEmpty())
		{
			 
		}
		else
		{
			swap(items[0], items[items.size() - 1]);
			int number= items[items.size() - 1];
			items.pop_back();

			bubbleDown(0);
			return number; 
		}

	}

	void bubbleDown(int x)
	{
		if (lchild(x) >= items.size())
		{
			
		}
		else
		{
		if (items[x] > items[lchild(x)] || items[x] >items[rchild(x)])
		{
			
			if (lchild(x) > rchild(x))
			{		
				swap(items[x], items[rchild(x)]);
				bubbleDown(rchild(x));
			}
				
			else if (rchild(x) > lchild(x))
			{
				swap(items[x], items[lchild(x)]);
				bubbleDown(lchild(x)); 
				
			}
				
		}

		}
		
	}

	void bubbleUp(int x)
	{
		if (items[x] < items[parent(x)])
		{
			swap(items[x], items[parent(x)]);
			bubbleUp(parent(x)); 
		}
	}

	void testDisplay()
	{
		for (int i = 0; i<items.size(); i++)
			cout << items[i] << endl;
	}
};

#include <iostream>
#include <string>
#include "heapsort.h"
using namespace std;

int main()
{
	////////////////////////////////////////////////
	//Step 1: Implement a basic min-heap priority queue
	////////////////////////////////////////////////
	minHeap pq;

	
	pq.insert(53);
	pq.insert(17);
	pq.insert(3);
	pq.insert(178);
	pq.insert(519);
	pq.insert(15);
	pq.insert(42);
	pq.insert(5);

	cout << "Extracting Minium: " << pq.extractMin()<<endl; //3
	cout << "Extracting Minium: " << pq.extractMin() << endl; //5
	cout << "Extracting Minium: " << pq.extractMin() << endl; //15
	cout << "Extracting Minium: " << pq.extractMin() << endl; //17

	pq.insert(93);
	pq.insert(2);
	pq.insert(7);
	pq.insert(83);

	cout << endl;

	pq.testDisplay();
	//2, 7, 42, 53, 83, 93, 178, 519

	
	while (!pq.isEmpty())
	{
		cout << "Extracting Minium: " << pq.extractMin() << endl;
	}
	cout << endl;

	int size = 30;
	for (int i = 0; i<size; i++)
	{
		pq.insert(rand());
	}

	//items should display in sorted order
	while (!pq.isEmpty())
	{
		cout << "Extracting Minium: " << pq.extractMin() << endl;
	}
	cout << endl;

       return 0; 
}

[clarkkent]

I got it to work

at some point i was comparint lchild(x) with rchild(x) its should have beeen items[lchild(x)] and items[rchild(x)]

[ne555]

> how would I perform a backtrace?
you write backtrace
http://ftp.gnu.org/old-gnu/Manuals/gdb-5.1.1/html_node/gdb_42.html