Documentation
¶
Overview ¶
adapted from https://github.com/cngkaygusuz/BrodalOkasakiHeap
The MIT License (MIT)
Copyright (c) 2015 ckaygusu ¶
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
adapted from https://github.com/cngkaygusuz/BrodalOkasakiHeap
The MIT License (MIT)
Copyright (c) 2015 ckaygusu ¶
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap struct {
// contains filtered or unexported fields
}
"Heap" is a wrapper around "HeapNode". This structure is defines an entrypoint for a Brodal-Okasaki heap and implements the priority queue interface using operations defined for "HeapNode" structure.
func (*Heap) Insert ¶
func (bq *Heap) Insert(value HeapElement)
Insert a new value to the heap. This function depends on another "insert" function, but executing this function always performs the insertion procedure of the skew-binomial heaps, which is simply described as follows:
- Get two nodes from the children of root node that has the minimum ranks.
- Skew-link those two nodes and the new node.
- Insert this newly linked node among the children of root.
Much of the logical complexity is hidden in the "skew-linking" procedure. Read "HeapNode.skewLink".
func (*Heap) Merge ¶
Instead of doing the merge operation immediately, we do it when we need it. This is also called "lazy-evaluation". Implementation of this operation is:
- Move the children head to the subqueue head.
- Insert the root of other queue as if it is a singleton node.
func (*Heap) Peek ¶
func (bq *Heap) Peek() HeapElement
Return the minimum valued element in the queue.
func (*Heap) Pop ¶
func (bq *Heap) Pop() HeapElement
Delete and return the minimum valued node. Since we do almost everything under Pop(), this function is a bit complicated. I implemented Pop() as follows:
- Get the minimum node among the children of root.
- If this node has elements in its subqueue, add them to the original queue.
- For every children of the minimum node; 3a. Insert the child again to the original heap.
All suboperations (1, 2, 3) take O(logn) time. As you can see, Pop() does every operation that takes O(logn) time, hence the asymptotical optimality. In the original paper, re-inserting the children of a node involves partitioning the children. I didn't bother understanding what the authors really meant, and made a slight modification here. Figure out the difference.
type HeapElement ¶
type HeapElement interface {
Value() int
}
Source Files