Like Tree1Likes
  • 1 Post By iMalc

Heap Sort Problem

This is a discussion on Heap Sort Problem within the C++ Programming forums, part of the General Programming Boards category; I am trying to implement heap sort. But i am not getting the correct output. I have a structure consiting ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    55

    Heap Sort Problem

    I am trying to implement heap sort.

    But i am not getting the correct output.

    I have a structure consiting of
    3 integets
    int u
    int v
    int weight

    i have then created a vector of the type of my structure, this all works fine
    I need to sort the vector by the weight attribute
    I can sort it using normal sort, like bubble etc, or std::sort, but I need to use HeapSort

    My code so far is:
    Code:
    void FixHeap(vector<Point>&HeapList, int n, int i)
    {
    	int j;
    	int data;
    
    	j=2*i;
    	data = HeapList[i].weight;
    
    	while(j<=n)
    	{
    		if((j<n)&&(HeapList[j].weight < HeapList[j+1].weight))
    		{
    			j=j+1;
    		}
    
    		if(data >= HeapList[j].weight)
    		{
    			break;
    		}
    		else
    		{
    			HeapList[j/2] = HeapList[j];
    		}
    		j = j*2;
    	}
    
    	HeapList[j/2].weight = data;
    }
    
    
    void MakeHeap(vector<Point>&HeapList, int n)
    {
    	int i;
    
    	for(i=n/2; i>=1; i--)
    	{
    		FixHeap(HeapList, n, i);
    	}
    }
    
    
    void HeapSort(vector<Point> &HeapList, int n)
    {
    	MakeHeap(HeapList, n);
    
    	int i;
    	int temp;
    
    	for(int i = n; i>1; i--)
    	{
    		temp = HeapList[i].weight;
    		HeapList[i] = HeapList[1];
    		HeapList[1] = temp;
    
    			FixHeap(HeapList, i-1, 1);
    	}
    }


    I call the function from the main using

    Code:
    HeapSort(myHeapList, myHeapList.size()-1);
    I am not sure where i am going wrong.

    Thank you.

  2. #2
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,533
    Why are you passing the vector's size along with the vector? One of the points of vectors are that the size is included. You should get rid of those arguments. Also, you should use the vectors own iterators to visit each item.
    It won't fix your problem, but at least it's still a good place to start, especially considering it'll make it more readable (and thus, more likely to get help).
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Your main problem is the formula for obtaining the children and parent of a node.
    The algorithm is often described in a manner that would make the head at index 1 and its children at indexes 2 and 3 (children = 2n and 2n+1, parent = n/2)
    However in practice arrays start at zero and so you need the head to be at index 0 and its children at indexes 1 and 2 (children = 2n-1 and 2n, parent = (n+1)/2)
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    iMalc: shouldn't it be parent = (n-1)/2 or am I missing something?

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by oogabooga View Post
    iMalc: shouldn't it be parent = (n-1)/2 or am I missing something?
    Ah yes, you're absolutely correct, thanks for noticing that. Too late to fix my post though.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Right. I probably should've PM'ed you so you could have fixed your post. Next time...

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Nah I was off watching youtube crap anyway
    laserlight likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Heap Sort Problem
    By bleda in forum C Programming
    Replies: 4
    Last Post: 01-18-2011, 06:04 PM
  2. heap sort
    By mherald81 in forum C Programming
    Replies: 16
    Last Post: 10-31-2010, 09:21 AM
  3. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 03:54 AM
  4. heap sort
    By lucaspewkas in forum C Programming
    Replies: 6
    Last Post: 05-02-2005, 04:20 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21