While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of some set, and each internal node is the $\max$ of its two children. I came up with a BuildHeap algorithm that's $O(n)$, a GetMax algorithm that's $O(1)$, an Insert algorithm that's $O(\log n)$, and a Delete algorithm that's $O(\log n)$. The number of nodes in this "heap" is $2n-1$ where $n$ is the number of elements in the underlying set. The structure is simpler than a binary heap.
Is there a name for this data structure?
import Data.List import Data.Ord data Heap a = Leaf a | Branch a (Heap a) (Heap a) deriving Show getMax :: Heap a -> a getMax (Leaf x) = x getMax (Branch x _ _) = x leaf :: Ord a => a -> Heap a leaf = Leaf branch :: Ord a => Heap a -> Heap a -> Heap a branch h1 h2 = Branch (max (getMax h1) (getMax h2)) h1 h2 buildHeap :: Ord a => [a] -> Heap a buildHeap xs = fst $ buildSubHeap (length xs) xs where buildSubHeap 1 (x:xs) = (Leaf x, xs) buildSubHeap n xs = let (leftSubHeap, remainder1) = buildSubHeap (div n 2) xs (rightSubHeap, remainder2) = buildSubHeap (n - div n 2) remainder1 in (branch leftSubHeap rightSubHeap, remainder2) insertIntoHeap :: Ord a => a -> Heap a -> Heap a insertIntoHeap x (Leaf y) = branch (leaf x) (leaf y) insertIntoHeap x (Branch m h1 h2) = branch h2 (insertIntoHeap x h1) deleteInsignificantElement :: Ord a => Heap a -> Heap a deleteInsignificantElement (Branch _ (Leaf x) (Leaf y)) = Leaf (max x y) deleteInsignificantElement (Branch _ h1 h2) = branch (deleteInsignificantElement h2) h1 getInsignificantElement :: Ord a => Heap a -> a getInsignificantElement (Branch _ (Leaf x) (Leaf y)) = min x y getInsignificantElement (Branch _ h1 h2) = getInsignificantElement h2 replaceMax :: Ord a => Heap a -> a -> Heap a replaceMax (Leaf x) y = Leaf y replaceMax (Branch m h1 h2) y | getMax h1 == m = branch (replaceMax h1 y) h2 | getMax h2 == m = branch h1 (replaceMax h2 y) | otherwise = undefined deleteMax :: Ord a => Heap a -> Heap a deleteMax heap = replaceMax (deleteInsignificantElement heap) (getInsignificantElement heap) data HeapObserver a = Singleton a | PushHeap a (Heap a) deriving Show popHeap :: Ord a => Heap a -> HeapObserver a popHeap (Leaf x) = Singleton x popHeap heap = PushHeap (getMax heap) (deleteMax heap) undown :: Down a -> a undown (Down x) = x heapsort :: Ord a => [a] -> [a] heapsort  =  heapsort xs = map undown . flattenHeap . buildHeap . map Down $ xs where flattenHeap heap = case popHeap heap of Singleton y -> [y] PushHeap y ys -> y : flattenHeap ys example_list = [234,234245,13235,14223,12,5,41,24,132,4134,25,234, 94875937, 34059, 784, 34875, 234, 765, 909] main :: IO () main = print (heapsort example_list == reverse (sort example_list))