Sorry, I'm not the one who seems to only have read headlines. A heap does not somehow entail a bubble sort. But let's leave the ad hominem out and look at facts.

Yes, you inspect log N item and move one, (steps 1, 2 and 3) below).

A single swap requires inspecting exactly two elements, not log n. You need at most log n swaps total at any time.

But then you are not finished. You still need to swap items 1 and 2.

Why? The heap condition is not violated at any point after your step 3 (which is really step 2, and swapping step 1). $a[0] > $a[1] and $a[0] > $a[2] is fulfilled, so the root and its children satisfy the condition. Likewise $a[1] > $a[3] and $a[1] > $a[4], so the left child of the root and its children satisfy the condition as well. $a[2] has no children, so it automatically satisfies the condition as well. Your step 4 is not required in a heap.

Want me to demonstrate on a larger heap? Sure.

X)  0 [ 13 ] 0)  0 [ 13 ] 1)  0 [ 13 ] 2)  0 [ 13 ] 3)  0 * 16 ]
    1 [ 12 ]     1 [ 12 ]     1 [ 12 ]     1 [ 12 ]     1 [ 12 ]
    2 [ 11 ]     2 [ 11 ]     2 [ 11 ]     2 * 16 ]     2 * 13 ]
    3 [ 10 ]     3 [ 10 ]     3 [ 10 ]     3 [ 10 ]     3 [ 10 ]
    4 [  9 ]     4 [  9 ]     4 [  9 ]     4 [  9 ]     4 [  9 ]
    5 [  8 ]     5 [  8 ]     5 * 16 ]     5 * 11 ]     5 [ 11 ]
    6 [  7 ]     6 [  7 ]     6 [  7 ]     6 [  7 ]     6 [  7 ]
    7 [  6 ]     7 [  6 ]     7 [  6 ]     7 [  6 ]     7 [  6 ]
    8 [  5 ]     8 [  5 ]     8 [  5 ]     8 [  5 ]     8 [  5 ]
    9 [  4 ]     9 [  4 ]     9 [  4 ]     9 [  4 ]     9 [  4 ]
   10 [  3 ]    10 [  3 ]    10 [  3 ]    10 [  3 ]    10 [  3 ]
   11 [  2 ]    11 * 16 ]    11 *  8 ]    11 [  8 ]    11 [  8 ]
   12 [  1 ]    12 [  1 ]    12 [  1 ]    12 [  1 ]    12 [  1 ]

[download]

That's it. 3 swaps among a segment of 12 elements.

In a heap with 100 elements, you need at most 7 swaps to get an item from the bottom of the heap to the top without violating the heap condition. I am doubtful of whether splice would win.

In a heap with 1,000 elements, you need at most 10 swaps. How much money will you bet on splice?

Makeshifts last the longest.

In reply to Re^9: Re-orderable keyed access structure? by Aristotle
in thread Re-orderable keyed access structure? by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.