Is there a name for this priority queue data structure? 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?

[edit]

Code:

import Data.List
import Data.Ord

data Heap a = Leaf a | Branch a (Heap a) (Heap a) deriving Show

getMax :: Heap a -&gt; a
getMax (Leaf x) = x
getMax (Branch x _ _) = x

leaf :: Ord a =&gt; a -&gt; Heap a
leaf = Leaf

branch :: Ord a =&gt; Heap a -&gt; Heap a -&gt; Heap a
branch h1 h2 = Branch (max (getMax h1) (getMax h2)) h1 h2

buildHeap :: Ord a =&gt; [a] -&gt; 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 =&gt; a -&gt; Heap a -&gt; 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 =&gt; Heap a -&gt; Heap a
deleteInsignificantElement (Branch _ (Leaf x) (Leaf y)) = Leaf (max x y)
deleteInsignificantElement (Branch _ h1 h2) = branch (deleteInsignificantElement h2) h1

getInsignificantElement :: Ord a =&gt; Heap a -&gt; a
getInsignificantElement (Branch _ (Leaf x) (Leaf y)) = min x y
getInsignificantElement (Branch _ h1 h2) = getInsignificantElement h2

replaceMax :: Ord a =&gt; Heap a -&gt; a -&gt; 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 =&gt; Heap a -&gt; Heap a
deleteMax heap = replaceMax (deleteInsignificantElement heap) (getInsignificantElement heap)

data HeapObserver a = Singleton a | PushHeap a (Heap a) deriving Show

popHeap :: Ord a =&gt; Heap a -&gt; HeapObserver a
popHeap (Leaf x) = Singleton x
popHeap heap = PushHeap (getMax heap) (deleteMax heap)

undown :: Down a -&gt; a
undown (Down x) = x

heapsort :: Ord a =&gt; [a] -&gt; [a]
heapsort [] = []
heapsort xs = map undown . flattenHeap . buildHeap . map Down $ xs
  where flattenHeap heap = case popHeap heap of
                           Singleton y -&gt; [y]
                           PushHeap y ys -&gt; 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))
This is essentially a Segment tree which is a data structure that augments an array with a binary tree as you describe such that:


You have fast set and get at any index
You have fast "aggregate" queries on ranges
You can support fast update queries on ranges, for some combinations of updates and queries


The $j$th node at height $k$ in the tree "summarizes" a subarray $[j*2^k, (j+1)*2^k)$ of the original array. Since each element of the array appears in only logarithmically many such subarrays, we can do updates in $O(\log n)$ time.

The range queries can use any associative operation. In your example the operation is $\max$, but other examples include sum, product, even standard deviation (via sum and sum of squares).



I originally called this a Fenwick Tree (aka Binary Indexed Tree), which is a similar structure but which compresses the tree into only exactly $n$ storage with no overhead(but loses access to the original array).