Implementing a Heap in Java – Part 1

This video shows how to implement the heap data structure in Java, one of a series of lessons in data structure and algorithms. In this first part, the algorithms for sift up and sift down are explained, followed by a description of how the heap items are stored in an array. Sesh Venugopal,

30 thoughts on “Implementing a Heap in Java – Part 1

  1. Another way to implement it as a data structure is to use an array but to make a filler spot for the first index, zero. That way to find the children, the formula would be either k*2 or k*2+1, personally I find this easier to implement. Good stuff professor!

  2. during the sift down, we compare the child nodes and swap with the greatest node for a max heap , is it the same for a min heap as well ? or do we swap with the smallest node ?

  3. This video is representing a Max-Heap data structure where the max element is always the root node. Please make sure to specify in the beginning of the video or change the title to "Implement a Max-Heap Data structure in Java". Great video though. Very informative and clear! Subscribed.

  4. Mister, can you help me with my project? we need to make a GUI program that will ask the user to enter numbers he want to sort and while performing the heap sort an animation is being done.

  5. Hi Sesh,
        Great video. At 8:25, I have  a question about what you mean by truncate fractional part. If you go through the proof for left and right. 
    that is                                                                   However for right, you end up with   
    i – index of left                                                    i – index of right
    i = 2p + 1                                                            i= 2p + 2
    you end up with                                                 you end up with  
    p = (i-1)/2                                                          p = (i – 2) / 2
    which makes sense 

    And i don't think that (i-1)/2 is the same as (i-2)/2
    Can you clarify this? The way our professor taught it was start with index 1 so it makes the math easier 

  6. You are describing it very smoothly, with many examples and clear view of the problem… You are working this step by step, so anyone really can follow up (y) 
    You are a great teacher 🙂 
    It would be really nice if you can videos for Bellman Ford and Floyd Warshall too…

  7. I really like how you break the idea into 2 parts, the theoretical part and then the implementation. This really makes it easy to understand. Thank you (Y)

  8. @ 7:59 , for the right child you to use the formula " k= 2p+1" when that is the formula for the left child. For the right child, should have used the formula " k = 2p + 2" which would have yielded " (k-2) /2. For the right child, 9, at index 2, this would have been (2-2)/2 = 0.

    Yes. The idea of integer division does yield the same result, but it is better to make use of the two formulas no?

Leave a Reply

Your email address will not be published. Required fields are marked *