CODEWITHSUNDEEP
algorithmsortingheapbinary-tree
Rahul Sundar
Rahul Sundar

Reputation: 490

Algorithm to delete root element from min or max heap

I have read the algorithm to delete the root element of heap. 1. Swap the root element with last element of the heap. 2. Then heapify (shift down) from the root element downwards.

At few other places, I find that they heapify upwards from the last element's parent towards root.(i.e., check deleteTop() function here http://www.geeksforgeeks.org/archives/14873) Hence confused with the right approach :-( Does this vary based on the situation or the article itself is wrong?

Upvotes: 1

Views: 1915

Answers (4)

Tarun Prakash Singh
Tarun Prakash Singh

Reputation: 21

The basic idea is to first make max heap.

A heap is nothing but ordering on elements of array which adhers to a[i] > a[2i+1] and a[2i+2] so you start with leaf nodes and swap , so you shift up.

But while building max heap, you can have to shift down too,read the below answer, I also had doubts before

Giving a test case where heap sort from Introduction to Algorithm fails

After the max heap or min heap is made , you swap with last element so you have the max element at its sorting position which is last.

Now since it was a max heap, the condition a[i] > a[2i+1] and a[2i+2] is followed at every index but at 0th location we are not sure whether its still following the condition ,as we have swapped from the last position and the new element at 0th place can be greater or smaller than its children.

so if it is smaller we swap, and we continue shift downwards until the heap property is satisfied and then we swap with n-1 position and continue.

So to answer your question, while building max heap we shift up and we will have to shift down too in case swapping leads to heap property violation.

but once we have made the max heap, and we swap with last element in that process we only shift downwards as heap property is satisfied at every position but 0th location.

Upvotes: 0

Avi Cohen
Avi Cohen

Reputation: 3414

The code of deleteTop() is wrong.

When given this max-heap and running deleteTop():

        10
     8      7
    5 4    3 2
        ||
        ||
        \/ 

        2
     8     7
    5 4   3 10
        ||
        ||
        \/ 

        7
     8     2
    5 4   3 10

The resulting heap is wrong since 2<(3 and 10)

Upvotes: 1

blackcompe
blackcompe

Reputation: 3190

At few other places, I find that they heapify upwards from the last element's parent towards root.(i.e., check deleteTop() function here http://www.geeksforgeeks.org/archives/14873)

The inline comments for heapify() clearly say the implementation was adapted for the median streaming problem; however, in a generic heap structure implementation, heapify() bubbles down. See this Algorithms lecture for a detailed explanation of heap implementation and the median streaming problem.

Upvotes: 0

Bharat Sinha
Bharat Sinha

Reputation: 14363

I believe the heap sorting concept is simply to identify the largest or smallest element and remove it from heap... you can do it either way so it's different implementation of the algorithm.

Upvotes: 0

Related Questions