README
¶
A double edge priorityQueue
it is developed based on "container/heap",which is a standard library
with this data structure,you can push data in it with O(logn) time-complexity,and get the min or max value of all the values in it with O(1) time-complexity. you can also use PopMax or PopMin to remove the max or min value in it. for now,it has not been able to remove any value from it yet.
some possible usage scenarios
- some algorithms problem which need frequently find max or min value
- to support a slide window which needs such characteristic ,for example ,it could be used for Linear scan register allocation.
License
This project is licensed under the MIT License - see the LICENSE file for details.
Documentation
¶
Overview ¶
a double end priority queue based on container/heap
Index ¶
- type PriorityDeque
- func (priorityDeque PriorityDeque) Len() int
- func (priorityDeque PriorityDeque) Max() any
- func (priorityDeque PriorityDeque) Min() any
- func (priorityDeque *PriorityDeque) PopMax() any
- func (priorityDeque *PriorityDeque) PopMin() any
- func (priorityDeque *PriorityDeque) Push(v any)
- func (priorityDeque *PriorityDeque) Replace(match func(any) bool, newV any)
- func (priorityDeque *PriorityDeque) ReplaceAll(match func(any) bool, newV any)
- func (priorityDeque *PriorityDeque) ReplaceMax(v any) any
- func (priorityDeque *PriorityDeque) ReplaceMin(v any) any
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PriorityDeque ¶
type PriorityDeque struct {
// contains filtered or unexported fields
}
func New ¶
func New(Less func(v1, v2 any) bool) *PriorityDeque
to use PriorityDeque ,you need to call this function to get a prepared one.
func (PriorityDeque) Len ¶
func (priorityDeque PriorityDeque) Len() int
get num of elements still in prioritydeque,taking O(1) time (which depends on a efficient built-in function len)
func (PriorityDeque) Max ¶
func (priorityDeque PriorityDeque) Max() any
get current max value,taking O(1) time
func (PriorityDeque) Min ¶
func (priorityDeque PriorityDeque) Min() any
get current min value,taking O(1) time
func (*PriorityDeque) PopMax ¶
func (priorityDeque *PriorityDeque) PopMax() any
remove and return the max value,taking O(logn) time
func (*PriorityDeque) PopMin ¶
func (priorityDeque *PriorityDeque) PopMin() any
remove and return the min value,which will take O(logn) time
func (*PriorityDeque) Push ¶
func (priorityDeque *PriorityDeque) Push(v any)
push any value in the priorityque,which will take O(logn) time
func (*PriorityDeque) Replace ¶ added in v1.0.0
func (priorityDeque *PriorityDeque) Replace(match func(any) bool, newV any)
replace one and only one certain value v where match(v)==true with new value newV
func (*PriorityDeque) ReplaceAll ¶ added in v1.0.0
func (priorityDeque *PriorityDeque) ReplaceAll(match func(any) bool, newV any)
replace all value where match(value)=true with new value newV
func (*PriorityDeque) ReplaceMax ¶ added in v0.3.0
func (priorityDeque *PriorityDeque) ReplaceMax(v any) any
this method will replace Max value with the given value,and Fix the heap from the place which equals to pop max value and push the given value in it,but will work faster,which takes O(logn) time the old max value will be returned
func (*PriorityDeque) ReplaceMin ¶ added in v0.3.0
func (priorityDeque *PriorityDeque) ReplaceMin(v any) any
this method will replace Min value with the given value,and Fix the heap from the place which equals to pop min value and push the given value in it,but will work faster,which takes O(logn) time the old min value will be returned
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
the example for how to use PriorityDeque
|
the example for how to use PriorityDeque |