How to delete from a Max-Heap?

If we put 15 in the root, what would be the process of heapify?

            85
            /\
           /  \
          /    \
        55      70
        /\      /\
       /  \    /  \
      22  33  30  65
     /\   /
   14 15 15

What should be the way to 开发者_Python百科delete 85 from the Heap?

As you are always swapping it with the larger of the two (heap property means that the parent is always larger than its children):

            15
            /\
           /  \
          /    \
        55      70
        /\      /\
       /  \    /  \
      22  33  30  65
     /\   
   14 15

            70
            /\
           /  \
          /    \
        55      15
        /\      /\
       /  \    /  \
      22  33  30  65
     /\   
   14 15

            70
            /\
           /  \
          /    \
        55      65
        /\      /\
       /  \    /  \
      22  33  30  15
     /\   
   14 15

If you delete 85 and replace it with 15, you turn the semi-heap back into a heap by downheaping, i.e. the 15 at the root will "sink" along the path of larger children. In this case it will swap with 70 then with 65.

Edit: because we are always swapping with the larger child, it ensures we end up with a valid heap (e.g. if we swapped our 15 with 55 instead of 70, we would have 70 as a child of 55 which is no good)

To add you put the new value as last (right to 20 in your example), and then you try to fix the heap, that is compare it with his parent, if it is larger the swap and compare again until no swap is needed (or you get to root)

In order to delete you remove you replace the last object (15 in you example) and fix the heap downward.

To delete 85 which is root here.

1. You can replace with the last leaf (15).
2. Heapify Again link to build heap