常用数据结构Go语言实现
[TOC]
栈
package stack
import (
"stack/stack"
"stack/stackwithcapacity"
)
type Stack interface {
// Push 添加一个元素
Push(interface{}) bool
// BatchPush 批量添加
BatchPush(...interface{}) bool
// Pop 弹出栈顶元素
Pop() (interface{}, bool)
// Top 获取栈顶元素
Top() (interface{}, bool)
// Empty 栈为空
Empty() bool
// Len 已使用大小
Len() int
}
// NewStack 创建一个栈
// if cap <= 0 return 无固定容量的栈
// else return 固定容量的栈
func NewStack(cap int) Stack {
if cap <= 0 {
return stack.NewStack()
}
return stackwithcapacity.NewStack(cap)
}基于链表实现的栈
添加元素时v.next = top.next使新添加节点指向虚拟头节点top的下一节点，而后top.next = v
移除元素时 记value = v.value，将 top.next = v.next; v.next = nil
package stack
import (
"container/list"
"sync"
)
type Stack struct {
lst *list.List
lock sync.RWMutex
}
// NewStack 创建一个栈
func NewStack() *Stack {
return &Stack{lst: list.New()}
}
// Push 元素入栈
func (stk *Stack) Push(val interface{}) bool {
stk.lock.Lock()
defer stk.lock.Unlock()
stk.lst.PushBack(val)
return true
}
// Pop 元素出栈
func (stk *Stack) Pop() (interface{}, bool) {
if stk.Empty() {
return nil, false
}
stk.lock.Lock()
defer stk.lock.Unlock()
// 移除尾节点
var v = stk.lst.Remove(stk.lst.Back())
return v, false
}
// Empty 栈是否为空
func (stk *Stack) Empty() bool {
return stk.Len() == 0
}
// Top 获取栈顶元素
func (stk *Stack) Top() (interface{}, bool) {
if stk.Empty() {
return nil, false
}
stk.lock.RLock()
defer stk.lock.RUnlock()
return stk.lst.Back().Value, true
}
// BatchPush 批量添加
func (stk *Stack) BatchPush(valList ...interface{}) bool {
stk.lock.Lock()
defer stk.lock.Unlock()
for i := 0; i < len(valList); i++ {
stk.lst.PushBack(valList[i])
}
return true
}
// Len 获取栈中元素个数
func (stk *Stack) Len() int {
return stk.lst.Len()
}基于slice实现固定容量的栈
添加元素时arr[top]=value; top++
移除元素时记v = arr[top], 然后top--，return v
实现如下
package stackwithcapacity
import "sync"
type Stack struct {
slice []interface{}
// 从0开始记
capacity int
// 从0开始记
use int
lock sync.RWMutex
}
func NewStack(capacity int) *Stack {
return &Stack{slice: make([]interface{}, capacity), capacity: capacity - 1, use: 0}
}
// Capacity 栈容量大小
func (stk *Stack) Capacity() int {
return stk.capacity + 1
}
// Len 栈中元素个数
func (stk *Stack) Len() int {
return stk.use
}
// Full 栈是否已满
func (stk *Stack) Full() bool {
return stk.use >= stk.capacity
}
// Push 栈有空间时可添加
func (stk *Stack) Push(val interface{}) bool {
if stk.Full() {
return false
}
stk.lock.Lock()
defer stk.lock.Unlock()
stk.slice[stk.use] = val
stk.use++
return true
}
// Usable 计算栈的可用空间
func (stk *Stack) Usable() int {
var usable = stk.capacity - stk.use
if usable >= 0 {
return usable
}
stk.use = stk.capacity
return 0
}
// BatchPush 批量添加
func (stk *Stack) BatchPush(valList ...interface{}) bool {
if len(valList) > stk.Usable() {
return false
}
stk.lock.Lock()
defer stk.lock.Unlock()
for i := 0; i < len(valList); i++ {
stk.slice[stk.use] = valList[i]
stk.use++
}
return true
}
// Empty 栈是否为空
func (stk *Stack) Empty() bool {
return stk.use == 0
}
// Pop 弹出元素
func (stk *Stack) Pop() (interface{}, bool) {
if stk.Empty() {
return nil, false
}
stk.lock.Lock()
defer stk.lock.Unlock()
var v = stk.slice[stk.use]
stk.use--
return v, true
}
// Top 获取栈顶元素
func (stk *Stack) Top() (interface{}, bool) {
if stk.Empty() {
return nil, false
}
stk.lock.RLock()
defer stk.lock.RUnlock()
return stk.slice[stk.use-1], true
}队列
package queue
import (
"queue/deque"
"queue/ringqueue"
)
type Deque interface {
Len() int
Head() interface{}
Tail() interface{}
Empty() bool
LAppend(x interface{}) bool
Append(x interface{}) bool
LPop() (interface{}, bool)
Pop() (interface{}, bool)
}
// NewDeque
// 如果指定了容量则选择循环队列
// 否则选择双端队列
func NewDeque(cap int) Deque {
if cap > 0 {
return ringqueue.NewRingQueue(cap)
}
return deque.NewDeque()
}双端队列
添加元素
// 记当前节点的后置节点为n
n := at.next
// 处理当前节点和新插入节点e的链接关系
at.next = e
e.prev = at
// 处理新插入节点e和当前节点原后置节点的关系
e.next = n
n.prev = e
e.list = l
// 链表长度加1
l.len++移除元素
// 使当前节点前驱节点指向当前节点的后置节点
e.prev.next = e.next
e.next.prev = e.prev
e.next = nil // avoid memory leaks
e.prev = nil // avoid memory leaks
e.list = nil
// 链表长度减1
l.len--package deque
import (
"container/list"
"sync"
)
type Deque struct {
// 队列
lst *list.List
lock sync.RWMutex
}
func NewDeque() *Deque {
return &Deque{lst: list.New()}
}
// Empty 是否为空
func (dq *Deque) Empty() bool {
dq.lock.RLock()
defer dq.lock.RUnlock()
return dq.lst.Len() == 0
}
// Len 当前队列长度
func (dq *Deque) Len() int {
return dq.lst.Len()
}
// LAppend 从左边添加元素, return是否添加成功
func (dq *Deque) LAppend(v interface{}) bool {
dq.lock.Lock()
defer dq.lock.Unlock()
var e = dq.lst.PushFront(v)
return e != nil
}
// LPop 从左边移除元素, return元素值、是否移除成功
func (dq *Deque) LPop() (interface{}, bool) {
if dq.Empty() {
return nil, false
}
dq.lock.Lock()
defer dq.lock.Unlock()
var v = dq.lst.Remove(dq.lst.Front())
return v, true
}
// Append 从右边添加元素, return是否添加成功
func (dq *Deque) Append(v interface{}) bool {
dq.lock.Lock()
defer dq.lock.Unlock()
var e = dq.lst.PushBack(v)
return e != nil
}
// Pop 从右边移除元素, return元素值、是否移除成功
func (dq *Deque) Pop() (interface{}, bool) {
if dq.Empty() {
return nil, false
}
dq.lock.Lock()
defer dq.lock.Unlock()
var v = dq.lst.Remove(dq.lst.Back())
return v, true
}
// Head 获取最左边元素
func (dq *Deque) Head() interface{} {
return dq.lst.Front()
}
// Tail 获取最右边元素
func (dq *Deque) Tail() interface{} {
return dq.lst.Back()
}环形队列
在队列未满的时候往尾部添加元素时q.nums[q.rear] = x，q.rear = (q.rear + 1) % q.lengthrear指针后移一位
在队列已满的时候往队列中添加元素则会被拒绝。
如果移除从队首移除元素，那么记v = q.nums[q.front]; q.front = (q.front + 1) % q.length
package ringqueue
import (
"sync"
)
// RingQueue 环形队列
type RingQueue struct {
front int // 指向队列头部第1个有效数据的位置
rear int // 指向队列尾部（即最后1个有效数据）的下一个位置，即下一个从队尾入队元素的位置
length int // 队列长度，capacity = length - 1
nums []interface{} // 队列元素
// lock
lock sync.RWMutex
}
// NewRingQueue 创建一个环形队列
func NewRingQueue(k int) *RingQueue {
var length = k + 1
return &RingQueue{
length: length,
nums: make([]interface{}, length),
}
}
func (q *RingQueue) Capacity() int {
return q.length - 1
}
// Len 获取队列中元素个数
func (q *RingQueue) Len() int {
q.lock.RLock()
defer q.lock.RUnlock()
if q.front > q.rear {
return q.rear - q.front + q.length
}
return q.rear - q.front
}
// Head 获取队首元素
func (q *RingQueue) Head() interface{} {
if q.Empty() {
return nil
}
return q.nums[q.front]
}
// Tail 获取队尾元素
func (q *RingQueue) Tail() interface{} {
if q.Empty() {
return nil
}
var pos int // 其实就是rear-1 //pos = (q.rear - 1 + q.length) % q.length
if q.rear > 0 {
pos = q.rear - 1
} else if q.rear == 0 {
pos = q.length - 1
}
return q.nums[pos]
}
// LAppend 从队首添加元素
func (q *RingQueue) LAppend(x interface{}) bool {
if q.IsFull() {
return false
}
q.lock.Lock()
defer q.lock.Unlock()
if q.front == 0 {
q.front = q.length - 1
} else {
q.front--
}
q.nums[q.front] = x
return true
}
// Append 从队尾添加元素
func (q *RingQueue) Append(x interface{}) bool {
if q.IsFull() {
return false
}
q.lock.Lock()
defer q.lock.Unlock()
q.nums[q.rear] = x
q.rear++ // q.rear = (q.rear + 1) % q.length // rear指针后移一位
if q.rear == q.length {
q.rear = 0
}
return true
}
// Pop 从队尾移除元素
func (q *RingQueue) Pop() (interface{}, bool) {
if q.Empty() {
return nil, false
}
q.lock.Lock()
defer q.lock.Unlock()
if q.rear == 0 {
q.rear = q.length - 1
} else {
q.rear--
}
// q.rear指向队列尾部（即最后1个有效数据）的下一个位置，即下一个从队尾入队元素的位置
// 上一个被Pop的元素即为q.rear
return q.nums[q.rear], true
}
// LPop 从队首添加元素
func (q *RingQueue) LPop() (interface{}, bool) {
if q.Empty() {
return nil, false
}
q.lock.Lock()
defer q.lock.Unlock()
var v = q.nums[q.front]
if q.front == q.length-1 { // front指针后移一位 // q.front = (q.front + 1) % q.length
q.front = 0
} else {
q.front++
}
return v, true
}
// Empty 队列是否为空
func (q *RingQueue) Empty() bool {
return q.front == q.rear
}
// IsFull 队列是否已满
func (q *RingQueue) IsFull() bool {
return (q.rear+1)%q.length == q.front
}优先队列
package priorityqueue
// 参考container/heap/example_pq_test.go
// An Item is something we manage in a priority queue.
type Item struct {
value interface{} // The value of the item; arbitrary.
priority int // The priority of the item in the queue.
index int // The index of the item in the heap.
}
// A PriorityQueue implements heap.*Item and holds Items.
type PriorityQueue []*Item
// NewPriorityQueue 新建一个优先队列
func NewPriorityQueue(items ...*Item) PriorityQueue {
return items
}
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
// We want Pop to give us the highest, not lowest, priority so we use greater than here.
return pq[i].priority > pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(item *Item) {
n := len(*pq)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() *Item {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil // avoid memory leak
item.index = -1 // for safety
*pq = old[0 : n-1]
return item
}
// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value interface{}, priority int) {
item.value = value
item.priority = priority
Fix(pq, item.index)
}
// heap
// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h *PriorityQueue) {
n := h.Len()
for i := n/2 - 1; i >= 0; i-- {
down(h, i, n)
}
}
// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h *PriorityQueue, x *Item) {
h.Push(x)
up(h, h.Len()-1)
}
// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h *PriorityQueue) *Item {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n)
return h.Pop()
}
// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h *PriorityQueue, i int) *Item {
n := h.Len() - 1
if n != i {
h.Swap(i, n)
if !down(h, i, n) {
up(h, i)
}
}
return h.Pop()
}
// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h *PriorityQueue, i int) {
if !down(h, i, h.Len()) {
up(h, i)
}
}
func up(h *PriorityQueue, j int) {
for {
i := (j - 1) / 2 // parent
if i == j || !h.Less(j, i) {
break
}
h.Swap(i, j)
j = i
}
}
func down(h *PriorityQueue, i0, n int) bool {
i := i0
for {
j1 := 2*i + 1
if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
break
}
j := j1 // left child
if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
j = j2 // = 2*i + 2 // right child
}
if !h.Less(j, i) {
break
}
h.Swap(i, j)
i = j
}
return i > i0
}并查集
查询元素4所在集合根节点，在查询过程中进行了路径压缩，查询完所在集合，也会使该节点直接指向集合根节点。
合并元素6所在集合和元素2所在集合，最开始找到两个元素各自所在集合的根节点，然后将其中一个集合的根节点指向另一个集合的根节点。
package disjointsets
type DSU []int
// ConstructorDSU 创建容量为n的并查集
// n指的是并查集中点的个数
func ConstructorDSU(n int) DSU {
var dsu = make(DSU, n)
// 初始化时每个节点的根节点就是自身
for i := 0; i < n; i++ {
dsu[i] = i
}
return dsu
}
// Find 查找a的根节点，并进行路径压缩（注意使用路径压缩的话，独立集合的根结点不能初始化为一个相同值，比如-1）
// 如`dsu[i] = -1`，这样在合并时求解是否存在环的时候所找根节点都会为-1而造成误判
func (dsu DSU) Find(a int) int {
if dsu[a] != a {
// 某个节点的根节点不是自身时
// 路径压缩
dsu[a] = dsu.Find(dsu[a])
}
// 获取到根节点
return dsu[a]
}
// Union 合并两个集合
// False: 说明已经在一个集合中，无需合并
// True: 合并成功
func (dsu DSU) Union(a, b int) bool {
var (
aRoot = dsu.Find(a)
bRoot = dsu.Find(b)
)
// 如果根节点相同说明已经在同一个集合中了
if aRoot == bRoot {
return false
}
// 将集合a加入到集合b中
dsu[aRoot] = bRoot
return true
}前缀树
package trie
type Trie interface {
Insert(string)
Search(string) bool
HasPrefix(string) bool
}
// Type 前缀树类型
type Type int32
const (
// EmHashTrie 哈希前缀树
EmHashTrie = iota
// EmListTrie 列表前缀树
EmListTrie
// EmArrayTrie 数组前缀树
EmArrayTrie
)
// NewTrie 创建一个Trie
func NewTrie(t Type) Trie {
switch t {
case EmHashTrie:
return NewHashTrie()
case EmListTrie:
return NewListTrie()
case EmArrayTrie:
return NewArrayTrie()
default:
// HashTrie较为通用
return NewHashTrie()
}
}ArrayTire
package trie
// ArrayTrie 数组前缀树
type ArrayTrie struct {
isWord bool
children [26]*ArrayTrie
}
var _ Trie = (*ArrayTrie)(nil)
// NewArrayTrie new arrayTrie
func NewArrayTrie() *ArrayTrie {
return &ArrayTrie{children: [26]*ArrayTrie{}}
}
// Insert 往前缀树中添加一个元素word
func (a *ArrayTrie) Insert(word string) {
var curNode = a
for i := 0; i < len(word); i++ {
if curNode.children[word[i]-'a'] == nil {
curNode.children[word[i]-'a'] = NewArrayTrie()
}
curNode = curNode.children[word[i]-'a']
}
curNode.isWord = true
}
// Search 查找前缀树中是否元素word
func (a *ArrayTrie) Search(word string) bool {
var _, has = a.search(word)
return has
}
func (a *ArrayTrie) search(word string) (*ArrayTrie, bool) {
var curNode = a
for i := 0; i < len(word); i++ {
if curNode.children[word[i]-'a'] == nil {
return nil, false
}
curNode = curNode.children[word[i]-'a']
}
return curNode, curNode.isWord
}
// HasPrefix 查询前缀树中是否存在前缀prefix
func (a *ArrayTrie) HasPrefix(prefix string) bool {
var curNode = a
for i := 0; i < len(prefix); i++ {
if curNode.children[prefix[i]-'a'] == nil {
return false
}
curNode = curNode.children[prefix[i]-'a']
}
return true
}ListTrie
package trie
// ListTrie 列表前缀树
type ListTrie struct {
isWord bool
char byte
children []*ListTrie
}
var _ Trie = (*ListTrie)(nil)
// NewListTrie new listTrie
func NewListTrie() *ListTrie {
return new(ListTrie)
}
// Insert 往前缀树中添加一个元素word
func (a *ListTrie) Insert(word string) {
var (
curNode = a
tNode *ListTrie
)
for i := 0; i < len(word); i++ {
if tNode = curNode.find(word[i]); tNode == nil {
curNode.children = append(curNode.children, &ListTrie{char: word[i]})
}
curNode = curNode.find(word[i])
}
curNode.isWord = true
}
func (a *ListTrie) find(c byte) *ListTrie {
for i := 0; i < len(a.children); i++ {
if a.children[i].char == c {
return a.children[i]
}
}
return nil
}
// Search 查找前缀树中是否元素word
func (a *ListTrie) Search(word string) bool {
var _, has = a.search(word)
return has
}
func (a *ListTrie) search(word string) (*ListTrie, bool) {
var curNode = a
for i := 0; i < len(word); i++ {
curNode = curNode.find(word[i])
if curNode == nil {
return nil, false
}
}
return curNode, curNode.isWord
}
// HasPrefix 查询前缀树中是否存在前缀prefix
func (a *ListTrie) HasPrefix(prefix string) bool {
var curNode = a
for i := 0; i < len(prefix); i++ {
curNode = curNode.find(prefix[i])
if curNode == nil {
return false
}
}
return true
}HashTrie
package trie
// HashTrie Hash前缀树
type HashTrie struct {
isWord bool
children map[byte]*HashTrie
}
var _ Trie = (*HashTrie)(nil)
// NewHashTrie new hashTrie
func NewHashTrie() *HashTrie {
return &HashTrie{children: make(map[byte]*HashTrie)}
}
// Insert 往前缀树中添加一个元素word
func (h *HashTrie) Insert(word string) {
var curNode = h
for i := 0; i < len(word); i++ {
if _, has := curNode.children[word[i]]; !has {
curNode.children[word[i]] = NewHashTrie()
}
curNode = curNode.children[word[i]]
}
curNode.isWord = true
}
// Search 查找前缀树中是否元素word
func (h *HashTrie) Search(word string) bool {
var _, has = h.search(word)
return has
}
func (h *HashTrie) search(word string) (*HashTrie, bool) {
var curNode = h
for i := 0; i < len(word); i++ {
if curNode.children[word[i]] == nil {
return nil, false
}
curNode = curNode.children[word[i]]
}
return curNode, curNode.isWord
}
// HasPrefix 查询前缀树中是否存在前缀prefix
func (h *HashTrie) HasPrefix(prefix string) bool {
var curNode = h
for i := 0; i < len(prefix); i++ {
if curNode.children[prefix[i]] == nil {
return false
}
curNode = curNode.children[prefix[i]]
}
return true
}线段树
package segmenttree
import (
"errors"
)
var (
// ErrIndexIllegal 索引非法
ErrIndexIllegal = errors.New("index is illegal")
)
package segmenttree
// Int64Merger 用户自定义区间内操作逻辑
type Int64Merger func(int64, int64) int64
type Int64Optimization func(int, int, int64) int64
// Int64SegmentTree 线段树
type Int64SegmentTree struct {
data []int64
tree []int64
lazy []int64
merge Int64Merger
optimization Int64Optimization
}
// NewInt64SegmentTree new Int64SegmentTree
func NewInt64SegmentTree(array []int64, merge Int64Merger) *Int64SegmentTree {
var seg = &Int64SegmentTree{
data: array,
tree: make([]int64, 4*len(array)),
lazy: make([]int64, 4*len(array)),
merge: merge,
}
seg.buildInt64SegmentTree(0, 0, seg.Size()-1)
return seg
}
// WithInt64Optimization 指定Int64Optimization来自定义区间[left, right]更新value的计算操作
func (s *Int64SegmentTree) WithInt64Optimization(f Int64Optimization) {
s.optimization = f
}
// leftChild 左子树index
func (s *Int64SegmentTree) leftChild(idx int) int {
return (idx << 1) + 1
}
// rightChild 右子树index
func (s *Int64SegmentTree) rightChild(idx int) int {
return (idx << 1) + 2
}
// buildInt64SegmentTree 建立线段树
func (s *Int64SegmentTree) buildInt64SegmentTree(idx int, left int, right int) {
if left == right {
s.tree[idx] = s.data[left]
return
}
var (
leftTreeIdx = s.leftChild(idx)
rightTreeIdx = s.rightChild(idx)
mid = left + (right-left)/2
)
// 创建左子树的线段树
s.buildInt64SegmentTree(leftTreeIdx, left, mid)
// 创建右子树的线段树
s.buildInt64SegmentTree(rightTreeIdx, mid+1, right)
// merge
s.tree[idx] = s.merge(s.tree[leftTreeIdx], s.tree[rightTreeIdx])
}
// Size 线段树元素数
func (s *Int64SegmentTree) Size() int {
return len(s.data)
}
// Get 索引原数组值
func (s *Int64SegmentTree) Get(idx int) (int64, error) {
if idx < 0 || idx >= s.Size() {
return 0, ErrIndexIllegal
}
return s.data[idx], nil
}
// Query 区间查询
func (s *Int64SegmentTree) Query(queryLeft int, queryRight int) (int64, error) {
if queryLeft > queryRight {
queryRight, queryLeft = queryLeft, queryRight
}
if queryLeft < 0 || queryRight >= s.Size() {
return 0, ErrIndexIllegal
}
return s.query(0, 0, s.Size()-1, queryLeft, queryRight), nil
}
func (s *Int64SegmentTree) query(idx int, left int, right int, queryLeft int, queryRight int) int64 {
if left == queryLeft && right == queryRight {
// 命中所查找区间
return s.tree[idx]
}
var (
mid = left + (right-left)/2
// 计算左右子节点下标
leftIdx = s.leftChild(idx)
rightIdx = s.rightChild(idx)
)
if queryLeft >= mid+1 {
// 所查询区间在右半部分
return s.query(rightIdx, mid+1, right, queryLeft, queryRight)
}
if queryRight <= mid {
// 所查询区间在左半部分
return s.query(leftIdx, left, mid, queryLeft, queryRight)
}
// 所查询区间分布在左右区间
return s.merge(
// 查询左部分
s.query(leftIdx, left, mid, queryLeft, mid),
// 查询右部分
s.query(rightIdx, mid+1, right, mid+1, queryRight),
)
}
// QueryLazy 懒惰查询
func (s *Int64SegmentTree) QueryLazy(queryLeft int, queryRight int) (int64, error) {
if queryLeft > queryRight {
queryRight, queryLeft = queryLeft, queryRight
}
if queryLeft < 0 || queryRight >= s.Size() {
return 0, ErrIndexIllegal
}
return s.queryLazy(0, 0, s.Size()-1, queryLeft, queryRight), nil
}
func (s *Int64SegmentTree) queryLazy(idx int, left int, right int, queryLeft int, queryRight int) int64 {
// 处理懒惰更新
s.pushDown(idx, left, right)
var (
mid = left + (right-left)>>1
leftIdx = s.leftChild(idx)
rightIdx = s.rightChild(idx)
)
if left > right || left > queryRight || right < queryLeft {
return 0
}
if queryLeft <= left && right <= queryRight {
// 在所查找区间范围内
return s.tree[idx]
}
if queryLeft >= mid+1 {
// 所查询区间在右半部分
return s.queryLazy(rightIdx, mid+1, right, queryLeft, queryRight)
}
if queryRight <= mid {
// 所查询区间在左半部分
return s.queryLazy(leftIdx, left, mid, queryLeft, queryRight)
}
// 所查询区间分布在左右区间
return s.merge(
// 查询左部分
s.queryLazy(leftIdx, left, mid, queryLeft, mid),
// 查询右部分
s.queryLazy(rightIdx, mid+1, right, mid+1, queryRight),
)
}
// Set 更新元素值
func (s *Int64SegmentTree) Set(index int, e int64) error {
if index < 0 || index >= s.Size() {
return ErrIndexIllegal
}
// 更新数组元素值
s.data[index] = e
// 更新tree元素值
s.set(0, 0, s.Size()-1, index, e)
return nil
}
func (s *Int64SegmentTree) set(idx int, left int, right int, index int, e int64) {
if left == right {
// 命中节点，更新元素值
s.tree[idx] = e
return
}
var (
leftIdx = s.leftChild(idx)
rightIdx = s.rightChild(idx)
mid = left + (right-left)/2
)
if index <= mid {
// idx在左边
s.set(leftIdx, left, mid, index, e)
} else {
// idx在右边
s.set(rightIdx, mid+1, right, index, e)
}
// merge
s.tree[idx] = s.merge(s.tree[leftIdx], s.tree[rightIdx])
}
// AddValueLazy
// 给[addLeft....addRight]位置的值都加上value
// 注意这里的更新值是在原来值的基础上增加或者减少，而不是把这个区间内的值都赋值为 x，区间更新和单点更新不同
// 这里的区间更新关注的是变化，单点更新关注的是定值
// 当然区间更新也可以都更新成定值，如果只区间更新成定值，那么 lazy 更新策略需要变化，merge 策略也需要变化，这里暂不详细讨论
func (s *Int64SegmentTree) AddValueLazy(addLeft int, addRight int, value int64) error {
if addLeft > addRight {
addRight, addLeft = addLeft, addRight
}
if addLeft < 0 || addRight >= s.Size() {
return ErrIndexIllegal
}
s.addValueLazy(0, 0, s.Size()-1, addLeft, addRight, value)
return nil
}
func (s *Int64SegmentTree) addValueLazy(idx int, left int, right int, addLeft int, addRight int, value int64) {
// 处理懒惰更新
s.pushDown(idx, left, right)
var (
mid = left + (right-left)>>1
leftIdx = s.leftChild(idx)
rightIdx = s.rightChild(idx)
)
if left > right || left > addRight || right < addLeft {
return
}
if addLeft <= left && right <= addRight {
// 正好在一个区间内区间
if s.optimization != nil {
s.tree[idx] = s.merge(s.tree[idx], s.optimization(left, right, value))
} else {
for i := 0; i < right-left+1; i++ {
s.tree[idx] = s.merge(s.tree[idx], value)
}
}
if left != right {
s.lazy[leftIdx] = s.merge(s.lazy[leftIdx], value)
s.lazy[rightIdx] = s.merge(s.lazy[rightIdx], value)
}
return
}
// 需要分别更新左右区间
s.addValueLazy(leftIdx, left, mid, addLeft, addRight, value)
s.addValueLazy(rightIdx, mid+1, right, addLeft, addRight, value)
s.tree[idx] = s.merge(s.tree[leftIdx], s.tree[rightIdx])
}
func (s *Int64SegmentTree) pushDown(idx int, left int, right int) {
var (
leftIdx = s.leftChild(idx)
rightIdx = s.rightChild(idx)
)
// 处理懒惰更新
if s.lazy[idx] != 0 {
if s.optimization != nil {
s.tree[idx] = s.merge(s.tree[idx], s.optimization(left, right, s.lazy[idx]))
} else {
// 懒惰更新根节点 如果是区间和则等同于：s.tree[idx] += (right-left+1)*s.lazy[idx]
for i := 0; i < right-left+1; i++ {
s.tree[idx] = s.merge(s.tree[idx], s.lazy[idx])
}
}
if left != right {
// 懒惰更新子节点 如果是区间求和则等同于：s.lazy[leftIdx] += s.lazy[idx]
s.lazy[leftIdx] = s.merge(s.lazy[leftIdx], s.lazy[idx])
s.lazy[rightIdx] = s.merge(s.lazy[rightIdx], s.lazy[idx])
}
// 消除懒惰更新标志
s.lazy[idx] = 0
}
}跳表
package skiplist
type ISkipList interface {
// Search 查找是否存在target
Search(target int) bool
// Add 添加元素
Add(num int)
// Erase 移除元素
Erase(num int) bool
}package skiplist
import (
"math"
"math/rand"
"sync"
)
const (
headValue = math.MinInt32
)
// SkipList 跳表
type SkipList struct {
// 虚拟头节点，最高层
head *node
// 层级
level int
// 链表长度
length int
// 锁
lock sync.RWMutex
}
// 节点
type node struct {
// 节点值
val int
// 右节点
right *node
// 下一级
down *node
}
func NewSkipList() *SkipList {
var sp = Constructor()
return &sp
}
func Constructor() SkipList {
return SkipList{
// 虚拟头节点
head: &node{
val: headValue,
}, //头节点 设置为一个极小的值
level: 1, //跳表层数，初始化为1级
length: 1, //原链表的个数（包括虚拟头节点）
}
}
// Search 查找是否存在target
// 由于设置了虚拟节点，那么意味着它存在的话，它必然是某个节点的右节点，就是说它前面一定有一个节点
func (s *SkipList) Search(target int) bool {
s.lock.RLock()
defer s.lock.RUnlock()
return s.getBefore(target, s.head) != nil
}
// Add 添加元素
func (s *SkipList) Add(num int) {
s.lock.Lock()
defer s.lock.Unlock()
var (
n = s.head
i int
nodes = make([]*node, s.level+1)
)
// 从最高层往下查找符合条件的节点
for n != nil {
for n.right != nil && n.right.val < num {
// 直到找到一个节点的下一个节点是大于目标值的
n = n.right
}
nodes[i] = n
i++
n = n.down
}
// 最后一个i是没有值的要去掉
i--
// 最底层链表添加新节点
var (
// 原链表的的前值
beforeNode = nodes[i]
newNode = &node{
val: num,
right: beforeNode.right,
}
)
beforeNode.right = newNode
s.length++
// 建立索引
for {
// 索引建立规则
if rand.Intn(2) == 0 || s.level > (s.length>>6)+1 {
break
}
if i > 0 {
// 从底层往上插入目标节点
i--
newNode = &node{
val: num,
right: nodes[i].right, // 连接右节点
down: newNode, // 连接下一层
}
// 前一节点与目标节点相连
nodes[i].right = newNode
} else {
// 新增层级
newNode = &node{
val: num,
down: newNode,
// 改节点是新层级的最后一个节点，因此没有右节点
}
// 虚拟节点
s.head = &node{
val: headValue,
right: newNode, // 向由连接新节点
down: s.head, // 向下连接前一虚拟节点
}
s.level++
}
}
}
// Erase 移除元素
func (s *SkipList) Erase(num int) bool {
s.lock.Lock()
defer s.lock.Unlock()
var (
target = num
before = s.getBefore(target, s.head)
)
if before == nil {
return false
}
// 逐级移除节点
for {
if before == nil {
break
}
// 移除目标节点
before.right = before.right.right
// 降级
before = before.down
// 继续寻找下一个满足条件的节点
before = s.getBefore(num, before)
}
s.length--
return true
}
// 获取目标值的前一个节点
func (s *SkipList) getBefore(target int, from *node) *node {
var n = from
for n != nil {
for n.right != nil && n.right.val < target {
// 如果n存在右节点
n = n.right
}
if n.right != nil && n.right.val == target {
// 找到了
return n
}
// 没找到到下一级找
n = n.down
}
// 没找到
return nil
}最后更新于
这有帮助吗？