deleting arbitrary node from a heap

This is a discussion on deleting arbitrary node from a heap within the C Programming forums, part of the General Programming Boards category; So I have a heap structure that I coded up, and it works well. My friend and I are working ...

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738

    deleting arbitrary node from a heap

    So I have a heap structure that I coded up, and it works well. My friend and I are working on a project together that uses this heap structure, and he informed me that we need a function that allows us to delete an arbitrary node from the heap instead of just the max node.

    So I went to code one up....

    I just wanted to make sure I have my logic correct though before I actually try and use this function. My logic is this:


    When we normally delete the max node from the heap (it's a max heap), we just take the node at the end of the array and move it up into the 0th spot. Then we heapify it.

    I figured, why not do that for any arbitrary node? The last node in the array is guaranteed to be a leaf node, so to delete any arbitrary node in the heap, do you think I could just move the last node in the array up to the index of the arbitrary node we are deleting, and the call heapify to restructure the heap and make sure it is good?

    Here is my code itself:

    Code:
    node* heap_extractNode(heap* myHeap, node *myNode) 
    {
    	int i;
    	node *nodeFound;
    
    	//Make sure the heap is not empty.  If it is empty, return NULL
    	if ( heap_isEmpty(myHeap) )
    		return NULL;
    
    	//Search for the node in the heap
    	for ( i = 0; i < myHeap->size; i++ )
    	{
    		if ( myHeap->nodes[i]->priority == myNode->priority &&
    			myHeap->nodes[i]->taskID == myNode->taskID )
    		{
    			nodeFound = myHeap->nodes[i];
    			myHeap->nodes[i] = myHeap->nodes[myHeap->size - 1];
    		}
    	}
    
    	myHeap->size = myHeap->size - 1;
    	
    	heap_heapify ( myHeap, 0 );
    	
    	return nodeFound;
    }
    My Website

    "Circular logic is good because it is."

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Maybe you should start the heapify process at i instead of at 0? (I'm assuming your heapify assumes a mostly-heap; if not, then never mind.)

  3. #3
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    Well certainly starting it at i instead of 0 would be more efficient

    That doesn't really matter to me though. I just wanted to know if my logic is sound, and that I am not completely screwing up the heap by deleting nodes in this manner.
    My Website

    "Circular logic is good because it is."

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Since you know that > is transitive, you know that a node is not just greater than it's children, but all its descendants. As long as you had a heap in the first place, moving a node halfway up and then heapifying can't hurt anything.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    Quote Originally Posted by DavidP View Post
    Well certainly starting it at i instead of 0 would be more efficient

    That doesn't really matter to me though. I just wanted to know if my logic is sound, and that I am not completely screwing up the heap by deleting nodes in this manner.
    Then you can rest assured that yes, that is how removal of an arbitrary node from a heap should be done.
    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. Help Debugging my AVL tree program.
    By Nextstopearth in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 01:48 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

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