heap

Documentation

Overview

Copyright 2009 The Go Authors. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package sort is my own implementation of different sort functions Package heap has functions for creating and abusing a heap. It is almost identically the same as containers/heap, so just use that.

Index

• func Init(h Interface)
• func Pop(h Interface) interface{}
• func Push(h Interface, val interface{})
• func Remove(h Interface, i int) (v interface{})
• type Interface

Functions

func Init

func Init(h Interface)

Creates a max heap out of an unorganized Interface collection. Runs in O(n) time, where n = h.Len().

func Pop

func Pop(h Interface) interface{}

Removes and returns the maximum of the heap and reorganizes. The complexity is O(lg n).

func Push

func Push(h Interface, val interface{})

This function will push a new value into a priority queue.

func Remove

func Remove(h Interface, i int) (v interface{})

Removes and returns the element at index i

Types

type Interface

type Interface interface {
	sort.Interface
	// Adds a value to the end of the collection.
	Push(val interface{})
	// Removes the value at the end of the collection.
	Pop() interface{}
}

Any type that implements Interface may be used as a max-tree. A tree must be either first Init()'d or build from scratch. The tree functions will panic if called inappropriately (as in, you cannot call Pop on an empty tree).

This interface embeds sort.Interface, meaning elements can be compared and swapped.

Note that Push and Pop are for this package to call. To add or remove elements from a tree, use tree.Push and tree.Pop.