Question About Heap Implementation - Topic

Member

Posts: 18,306

Joined: Dec 13 2008

Gold: 350.00

Nov 23 2014 07:42pm

I'm having an issue with upheap after inserting an item into a heap implemented as an array

When inserting random numbers from 0 to 100, printing the array results in this:

Code

void HeapSort::bubbleUp()
{
int i = numOfElements;
int parent = 0;

while (i > 0)
{
parent = floor((i - 1) / 2);

if (heap[parent] < heap[i])
{
i = 0;
}
else
{
swap(parent, i);
i = parent;
}
}
}

Minkomonster

Member

Posts: 1,995

Joined: Jun 28 2006

Gold: 7.41

Nov 23 2014 08:05pm

Typically a Heap BubbleUp is implemented like so:

Code

function bubble_up
int current_index = number_of_nodes;

while( node_has_parent(current_index) && parent_node(current_index) > current_node(current_index) )
//if the current node has a parent and that parent is greater than it then they are out of order
swap_nodes(current_index, parent_index(current_index));
current_index = parent_index(current_index);
end_while
end_function

Netorare

Member

Posts: 18,306

Joined: Dec 13 2008

Gold: 350.00

Nov 23 2014 08:14pm

Quote (Minkomonster @ Nov 23 2014 06:05pm)

Typically a Heap BubbleUp is implemented like so:

Code

I'm still getting the same output implementing it that way

Minkomonster

Member

Posts: 1,995

Joined: Jun 28 2006

Gold: 7.41

Nov 23 2014 08:16pm

And if the output is incorrect, then your math in determining the indicies are incorrect.

Netorare

Member

Posts: 18,306

Joined: Dec 13 2008

Gold: 350.00

Nov 23 2014 08:54pm

oops, I forgot to take into account starting at index 0, so i would have had to start at 'int i = numOfElements - 1'

but its still not sorting correctly rip

carteblanche

Member

Posts: 32,925

Joined: Jul 23 2006

Gold: 3,804.50

Nov 23 2014 09:00pm

Quote (Tricon @ Nov 23 2014 09:54pm)

oops, I forgot to take into account starting at index 0, so i would have had to start at 'int i = numOfElements - 1'

but its still not sorting correctly rip

i suggest you stop worrying about the entire sort for a moment and check if your heap works correctly first. draw it out by hand for each iteration, and compare it to what your code transforms it into.

Netorare

Member

Posts: 18,306

Joined: Dec 13 2008

Gold: 350.00

Nov 23 2014 09:05pm

nevermind for now

This post was edited by Tricon on Nov 23 2014 09:07pm

Minkomonster

Member

Posts: 1,995

Joined: Jun 28 2006

Gold: 7.41