maruks.data

Persistent data structures based on "Purely Functional Data Structures" book.

Leftist heap

Leftist heap implements persistent stack operations:

operation		time complexity
peek	returns the smallest element	O(1)
pop	removes the smallest element	O(log n)
conj	adds element to the heap	O(log n)
count	returns heap's size	O(n)
empty	returns empty heap	O(1)
seq	returns sequence of all elements	O(n log n)
=	compares with other sequence	O(n log n)
toString	returns string representation	O(n log n)

Examples

=> (require '[maruks.data.leftist-heap :refer [heap min-heap max-heap]])

We can use min-heap or max-heap to create a heap:

=> (min-heap 9 7 5 3)  
#<LeftistHeap 3 5 7 9>
=> (max-heap 9 7 5 3)  
#<LeftistHeap 9 7 5 3>

No-args factory functions return empty heap:

=> (empty? (max-heap))  
true

We can use custom comparator function:

=> (heap #(<= (count %1) (count %2)) "hkjlm" "defg" "abc")
#<LeftistHeap abc defg hkjlm>

conj adds an element to heap:

=> (conj (heap #(<= (count %1) (count %2))) "heaps!!!")
#<LeftistHeap heaps!!!>

pop returns heap with the smallest element removed:

(pop (heap #(<= (count %1) (count %2)) "hkjlm" "defg" "abc"))
#<LeftistHeap defg hkjlm>

Smallest element:

=> (peek (max-heap 9 8 7 6))
9

seq returns all elements in sorted order:

=> (seq (min-heap 9 7 5 3))
(3 5 7 9)

Heaps are countable:

=> (count (max-heap 9 7 5 3) ) 
4

License

Copyright © 2015 Maris

Distributed under the Eclipse Public License version 1.0