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\$
  • \$\begingroup\$ No builtins, I'm guessing? \$\endgroup\$ – Sp3000 Jan 15 '15 at 1:34
  • \$\begingroup\$ @Sp3000 Any built in heap type or methods operating on that type are disallowed, yes. \$\endgroup\$ – globby Jan 15 '15 at 1:36
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\$
  • \$\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 '15 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 '15 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\$
  • 1
    \$\begingroup\$ Invalid because it is using arrays instead of data structures. See the clarifications \$\endgroup\$ – globby Jan 16 '15 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\$ – YoYoYonnY Jan 19 '15 at 18:05
  • \$\begingroup\$ It wasn't implemented with a custom class, type, or struct. It's an invalid solution. \$\endgroup\$ – globby Jan 19 '15 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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