# Challenge

You must, in the least bytes possible, implement the Binary Heap data structure and each of the following methods that operate on it:

• A function which takes no arguments and returns an empty Heap
• A function which takes a list of arguments with an arbitrary length and returns a Heap containing the elements
• A function which takes two Heaps and merges them into a new Heap, returning it
• A function which removes the root element of the Heap and reorders it accordingly, returning the root and new Heap
• A function which takes an integer and a Heap, inserts it into the Heap, and returns the Heap

# Clarifications

• Your heap must be implemented as linking nodes created with structs, classes, custom types or equivalent, not using an array or list
• You may implement either a max-heap or a min-heap, it is your choice.
• You may assume that only integers are being stored in the heap
• Your functions must be bound to a variable or name (and callable, obviously)
• Standard loopholes are disallowed

## Resources

• No builtins, I'm guessing? – Sp3000 Jan 15 '15 at 1:34
• @Sp3000 Any built in heap type or methods operating on that type are disallowed, yes. – globby Jan 15 '15 at 1:36

Golfed version

data H=H H Int H|E
l E=0
l(H a _ b)=1+l a+l b
i E x=H E x E
i(H a y b)x|l a>l b=H a u$i b v|1>0=H(i a v)u b where(u,v)|x>y=(x,y)|1>0=(y,x) f=foldl i E t E=[] t(H a x b)=x:t a++t b m a b=f$t a++t b
p(H a x b)=(x,m a b)


Same, but with meaningfull names. Straightforward heap implemented as a binary tree, it can be either Empty or Heap leftBranch element rightBranch.

data Heap=Heap Heap Int Heap|Empty
len Empty=0
len(Heap a _ b)=1+len a+len b
insert Empty x=Heap Empty x Empty
insert(Heap a y b)x
|len a>len b=Heap a u$insert b v |1>0=Heap(insert a v)u b where (u,v)|x>y=(x,y) |1>0=(y,x) fromList=foldl insert Empty toList Empty=[] toList(Heap a x b)=x:toList a++toList b merge a b=fromList$toList a++toList b
pop(Heap a x b)=(x,merge a b)

• I'm largely unfamiliar with Haskell so I'm having some trouble following this. Could you please add some explanation? – Alex A. Jan 20 '15 at 20:46
• @Alex It is very readable code without any haskell knowledge imo. Functions perform pattern matching on the Heap datatype and do the obvious things :) – swish Jan 20 '15 at 23:20

## Lua - 275 (Already lost :D)

function f(s)return loadstring(s)end;f(([[a=f"_{}"b=f"t={...}&sort(t)_t"c=f"z={...}_f('x={'..&concat(z,',')..','..&concat(z,',')..'}&sort(x)_x')()"d=f"z={...}z=zr=z[#z]&remove(z,#z)_z,r"e=f"z={...}&insert(z,z)_z"]]):gsub("&","table."):gsub("_","return "))()


How it works:

function newHeap()
return {}
end
function insertItemsToHeap(...)
heap = {...}
table.sort(heap)
return heap
end
function margeHeaps(heap1, heap2)
table.sort(x)
return x
end
function removeRoot(...)
z = {...}
z = z
r = z[#z]
table.remove(z,#z)
return z, r
end
function insertInt(heap, int)
table.insert(heap, int)
return heap
end


Note: I have no previous experience with Binary Heaps once however, hope this is right.

• Invalid because it is using arrays instead of data structures. See the clarifications – globby Jan 16 '15 at 0:23
• Lua tables are not arrays (list of items with a specific type/size) but more like objects (list of keys with values of any type). Moreover, people argue that Lua tables are a class like data structure, because their metatables allow for complex class-like behavior (Operator overloads, stuff like that). I did use the built-in table library, but that was not disallowed. – YoYoYonnY Jan 19 '15 at 18:05
• It wasn't implemented with a custom class, type, or struct. It's an invalid solution. – globby Jan 19 '15 at 20:28