Talk:Skew heap

Incorrect/misleading diagram

While the layout of the corresponding section implies otherwise, the skew heap shown in the "after" part of the first diagram can't have been produced by running the presented C++ code, as the operation implemented by the function _Merge() is not the "full-traversal" top-down skew heap union operation, but its "shortcut" version that traverses the right paths of the melded heaps from the top down, merging them and simultaneously swapping left and right children, but only until the bottom of one of the paths is reached, at which point the remainder of the other path is simply attached to the bottom of the merge path and the process terminates (immediately) [1 p58]. Thus, even though melding the two sample heaps from the "before" part of the diagram by using _Merge() would give us a tree having the exact same shape, the nodes "201" and "105" would be swapped – or rather, I should say "would not be swapped" (they're swapped now; when using _Merge(), the node "99" wouldn't have their children exchanged to begin with). The same applies to the Haskell program shown at the end of the article – running

test :: IO ()
test = do
    print $ union h1 h2
  where
    h1 = Node 1
            (Node 4
                (Node 63
                    Empty
                    Empty)
                (Node 24
                    Empty
                    Empty))
            (Node 23
                (Node 44
                    Empty
                    Empty)
                (Node 28
                    Empty
                    Empty))
    h2 = Node 13
            (Node 17
                (Node 57
                    Empty
                    Empty)
                (Node 49
                    Empty
                    Empty))
            (Node 99
                (Node 105
                    Empty
                    Empty)
                (Node 201
                    Empty
                    Empty))

outputs

Node 1
    (Node 13
        (Node 23
            (Node 28
                (Node 99
                    (Node 105
                        Empty
                        Empty)
                    (Node 201
                        Empty
                        Empty))
                Empty)
            (Node 44
                Empty
                Empty))
        (Node 17
            (Node 57
                Empty
                Empty)
            (Node 49
                Empty
                Empty)))
    (Node 4
        (Node 63
            Empty
            Empty)
        (Node 24
            Empty
            Empty))

Kamil Kurkiewicz (talk) 12:30, 20 May 2021 (UTC)