# 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?

Code:

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))


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).

• I think you're right and I confuse them all the time – Curtis F Jan 26 '19 at 22:39
• For clarification: a Segment tree also uses linear storage. – Jakube Jan 26 '19 at 23:12

You've just reinvented a range-query structure. This is an instance of the more general idea that, if you put all data at only the leaves of a binary tree, you can use internal nodes to represent substructures, and it will work for any kind of structure that can be recursively defined with an $$O(1)$$ recursive initialization.

In this case, you can see that the structure is just an unordered set with a maximum, which is obviously $$O(1)$$ recursively definable. It is also clear that you can support Insert and DeleteMax and $$O(1)$$ GetMax, but not $$O(\log n)$$ Search. Additionally, if you think a bit you should be able to figure out how to support $$O(\log n)$$ MergeHeap.