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;
}