Answer to Problem
|
In each case below, the heap is in black, while those nodes that are no longer part of the heap are in red. At each stage, the two elements in blue are interchanged, and the heap property restored for element 1 down through the element before the second blue element.
___ 1/ \ \ 7/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 29/ \ 10/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 14/ \ 8/ \ 9/ \ 2/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 3/ \ 11/ --- ---
___ 1/ \ \ 29/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 14/ \ 10/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 11/ \ 8/ \ 9/ \ 2/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 3/ \ 7/ --- ---
___ 1/ \ \ 14/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 11/ \ 10/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 7/ \ 8/ \ 9/ \ 2/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 3/ \ 29/ --- ---
___ 1/ \ \ 11/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 8/ \ 10/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 7/ \ 3/ \ 9/ \ 2/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 14/ \ 29/ --- ---
___ 1/ \ \ 10/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 8/ \ 9/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 7/ \ 3/ \ 2/ \ 11/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 14/ \ 29/ --- ---
___ 1/ \ \ 9/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 8/ \ 2/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 7/ \ 3/ \ 10/ \ 11/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 14/ \ 29/ --- ---
___ 1/ \ \ 8/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 7/ \ 2/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 3/ \ 9/ \ 10/ \ 11/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 14/ \ 29/ --- ---
___ 1/ \ \ 7/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 3/ \ 2/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 8/ \ 9/ \ 10/ \ 11/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 14/ \ 29/ --- ---
___ 1/ \ \ 3/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 2/ \ 7/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 8/ \ 9/ \ 10/ \ 11/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 14/ \ 29/ --- ---
___ 1/ \ \ 2/ +-------------------------------+ | | ___ ___ 2/ \ 3/ \ \ 3/ \ 7/ +---------------+ +---------------+ | | | | ___ ___ ___ ___ 4/ \ 5/ \ 6/ \ 7/ \ \ 8/ \ 9/ \ 10/ \ 11/ +-------+ | | ___ ___ 8/ \ 9/ \ \ 14/ \ 29/ --- ---