5
\$\begingroup\$

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

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

2 Answers 2

3
\$\begingroup\$

Haskell - 217

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)
\$\endgroup\$
2
  • \$\begingroup\$ I'm largely unfamiliar with Haskell so I'm having some trouble following this. Could you please add some explanation? \$\endgroup\$
    – Alex A.
    Jan 20, 2015 at 20:46
  • \$\begingroup\$ @Alex It is very readable code without any haskell knowledge imo. Functions perform pattern matching on the Heap datatype and do the obvious things :) \$\endgroup\$
    – swish
    Jan 20, 2015 at 23:20
-1
\$\begingroup\$

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[1],',')..','..&concat(z[2],',')..'}&sort(x)_x')()"d=f"z={...}z=z[1]r=z[#z]&remove(z,#z)_z,r"e=f"z={...}&insert(z[1],z[2])_z[1]"]]):gsub("&","table."):gsub("_","return "))()

How it works:

function newHeap()
    return {}
end
function insertItemsToHeap(...)
    heap = {...}
    table.sort(heap)
    return heap
end
function margeHeaps(heap1, heap2)
    x = loadstring("return {"..table.concat(heap1,",")..","..table.concat(heap2,",").."}")()
    table.sort(x)
    return x
end
function removeRoot(...)
    z = {...}
    z = z[1]
    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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Invalid because it is using arrays instead of data structures. See the clarifications \$\endgroup\$
    – globby
    Jan 16, 2015 at 0:23
  • \$\begingroup\$ 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. \$\endgroup\$
    – yyny
    Jan 19, 2015 at 18:05
  • \$\begingroup\$ It wasn't implemented with a custom class, type, or struct. It's an invalid solution. \$\endgroup\$
    – globby
    Jan 19, 2015 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.