Heap

The heappermutations package implements primitives to generate all possible permutations following Heap's algorithm on typed collection.

Package sliceheap returns a quick heap interface implementation given a pointer to a slice and a less function (akin to sort.Slice for sorting slices). This package is for that rare time when you need a heap and do not want to make an arbitrary type to provide Push and Pop.

Package medianheap implements a running median algorithm for integers using 2 heaps. The provided operations are for adding elements and retrieving the median. The time complexity for updating the median is O(logN), retrieving it O(1). The median value is equal to the k/2th element of a sorted array of size k if k is odd, or (k/2)-1th element if size is even. No averages are computed. Here is equivalent code (with time complexity O(N logN)):

This example shows a use in the Heapsort algorithm This example shows how to implement your own CompareFunc and the use on a defined type

Package fibheap provides a standard Fibonacci heap pointer implementation. The nodes are linked in a doubly-linked circular list. The parent nodes have a pointer to the left-most child, while all children have a reference to their parent

Package heapq implements a generic heap-structured priority queue.

Package heap implements indexed minimum Fibonacci priority queue.

Package goque provides embedded, disk-based implementations of stack, queue, and priority queue data structures. Motivation for creating this project was the need for a persistent priority queue that remained performant while growing well beyond the available memory of a given machine. While there are many packages for Go offering queues, they all seem to be memory based and/or standalone solutions that are not embeddable within an application. Instead of using an in-memory heap structure to store data, everything is stored using the Go port of LevelDB (https://github.com/syndtr/goleveldb). This results in very little memory being used no matter the size of the database, while read and write performance remains near constant. See README.md or visit https://github.com/beeker1121/goque for more info. ExampleObject demonstrates enqueuing a struct object. ExamplePrefixQueue demonstrates the implementation of a Goque queue. ExamplePriorityQueue demonstrates the implementation of a Goque queue. ExampleQueue demonstrates the implementation of a Goque queue. ExampleStack demonstrates the implementation of a Goque stack.

Package securecookie is a fast, efficient and safe cookie value encoder/decoder. A secure cookie has its value ciphered and signed with a message authentication code. This prevents the remote cookie owner from knowing what information is stored in the cookie or modifying it. It also prevents an attacker from forging a fake securecookie. What makes this secure cookie package different is that it is fast (faster than the Gorilla secure cookie), and the value encoding and decoding needs no heap allocations. The intended use is to instantiate all secure cookie objects of your web site at program start up. In the following example "session" is the cookie name. The key is a byte sequence generated with the GenerateRandomKey() function. The same key must be used to retrieve the value. An securecookie can also be instantiated as a global variable with the MustNew function. The function will panic if an error occurs. A securecookie object is immutable. It's methods can be called from different goroutines. The Delete(), SetValue() and GetValue() methods are independent. To set a cookie value, call the SetValue() method with a http.ResponseWriter w, and a value val as arguments. A securecookie value is retrieved from an http.Request with the GetValue() method and is appended to the given buffer, extending it if required. If buf is nil, a new buffer is allocated. A securecookie is deleted by calling the Delete() method with the http.ResponseWriter w as argument.

Package fastheap provides a heap implementation specialized on numeric keys and arbitrary stored values. It is faster than containers/heap cause it doesn't use interface call for comparisons, and it manipulates storage by itself. Also, it uses 4 way heap instead of binary heap. May be it makes a deal with CPU cache :)

Package pprof serves via its HTTP server runtime profiling data in the format expected by the pprof visualization tool. For more information about pprof, see http://code.google.com/p/google-perftools/. The package is typically only imported for the side effect of registering its HTTP handlers. The handled paths all begin with /debug/pprof/. To use pprof, link this package into your program: If your application is not already running an http server, you need to start one. Add "net/http" and "log" to your imports and the following code to your main function: Then use the pprof tool to look at the heap profile: Or to look at a 30-second CPU profile: Or to look at the goroutine blocking profile: To view all available profiles, open http://localhost:6060/debug/pprof/ in your browser. For a study of the facility in action, visit

Package heap implements a very similar function to the builtin heap(priority queue) package except the elements are not necessarily interface{}, but can be any type. The trick is using the last element as the in/out place. Push/Pop/Remove are replaced with PushLast/PopToLast/RemoveToLast, respectively. An heap with int value can be easily implemented as follow:

Package fheap implements the the Fibonacci Heap. This example illustrates queing and dequeuing from a Fibonacci heap.

TODO : update An off-heap hash-table for Go (golang). Originally called go-offheap-hashtable, but now shortened to just offheap. The purpose here is to have a hash table that can work away from Go's Garbage Collector, to avoid long GC pause times. We accomplish this by writing our own Malloc() and Free() implementation (see malloc.go) which requests memory directly from the OS. The keys, values, and entire hash table is kept on off-heap storage. This storage can also optionally be backed by memory mapped file for speedy persistence and fast startup times. Initial HashTable implementation inspired by the public domain C++ code of See also for performance studies of the C++ code. The implementation is mostly in offheap.go, read that to start. Maps pointer-sized integers to Cell structures, which in turn hold Val_t as well as Key_t structures. Uses open addressing with linear probing. This makes it very cache friendly and thus very fast. In the t.Cells array, UnHashedKey = 0 is reserved to indicate an unused cell. Actual value for key 0 (if any) is stored in t.ZeroCell. The hash table automatically doubles in size when it becomes 75% full. The hash table never shrinks in size, even after Clear(), unless you explicitly call Compact(). Basic operations: Lookup(), Insert(), DeleteKey(). These are the equivalent of the builtin map[uint64]interface{}. As an example of how to specialize for a map[string]*Cell equivalent, see the following functions in the bytekey.go file: Example use: Note that this library is only a starting point of source code, and not intended to be used without customization. Users of the HashTable will have to customize it by changing the definitions of Key_t and Val_t to suite their needs. I'm experimenting next with storing objects in Capnproto serialized format, but this branch (branch capnp) isn't quite ready for use. Related ideas: https://gist.github.com/mish15/9822474 (using CGO) https://groups.google.com/forum/#!topic/golang-nuts/kCQP6S6ZGh0 not fully off-heap, but using a slice instead of a map appears to help GC quite alot too: https://github.com/cespare/kvcache/blob/master/refmap.go

goheap is a simple implementation of the heap data structure and sorting algorithm. Its intention is for learning purposes of the Go language.

Example of using github.com/dengliu/gocommon/heap import ( )