go --- container / heap 자세히 알 아 보기

5806 단어 골 랑 어
목차
container / heap 이 뭐 예요?
container / heap 제공 방법
container / heap 의 원본 코드
container / heap 용도
1. int slice 타 입의 작은 뿌리 더미
2. 우선 순위 대기 열 구현 (중요: k8s 우선 순위 대기 열)
3. 최소 K 개수 또는 최대 K 개 수 를 처리 하고 대량의 데 이 터 를 처리 합 니 다.
container / heap 이 뭐 예요?
더미 (영어: heap) 는 컴퓨터 과학 에서 특수 한 데이터 구 조 를 통칭 한다. 더 미 는 보통 나무 로 볼 수 있 는 배열 대상 이다. 더 미 는 항상 다음 과 같은 성질 을 만족시킨다.
  • 더미 의 특정한 노드 의 값 은 항상 아버지 노드 의 값 보다 크 거나 작 지 않다.
  • 더 미 는 항상 완전 이 진 트 리 한 그루 이다.
  • 뿌리 노드 의 가장 큰 더 미 를 최대 더미 나 큰 뿌리 더미 라 고 하고 뿌리 노드 의 가장 작은 더 미 를 최소 더미 나 작은 뿌리 더미 라 고 한다.
  • 더미 의 초기 화. 어떻게 초기 화 하 는 지, 큰 뿌리 더미 와 작은 뿌리 더 미 를 구축 하 는 지
  • 더미 의 삽입 요소 와 삭제 요소
  • 더미 의 정렬
  • 더미 의 위로 조정 함수 와 아래로 조정 함수
  • 상술 한 네 가지 문 제 를 이해 한 후에 소스 코드 를 보면 더욱 명확 하 게 실 현 될 것 이다.
    container / heap 제공 방법container/heap 작은 뿌리 더미, 즉 각 노드 의 값 은 하위 트 리 의 모든 요소 의 값 보다 작 습 니 다. 힙 백 은 heap.Interface 의 유형 을 실현 하기 위해 쌓 는 방법 을 제공 합 니 다. Init / Push / Pop / Remove / Fix.heap.Interfacesort.Interface 가 포함 되 어 있 기 때문에 목표 유형 은 다음 과 같은 방법 을 포함해 야 한다. Len / Less / Swap, Push / PP.
    type Interface interface {
        sort.Interface
        Push(x interface{}) // add x as element Len()
        Pop() interface{}   // remove and return element Len() - 1.
    }

    container / heap 의 원본 코드
    문장 분석 참조:https://studygolang.com/articles/13173
    func Fix(h Interface, i int) //    i    ,             O(log(n)),  n  h.Len()。         
    func Init(h Interface)  //      。                  。    O(n)
    func Pop(h Interface) interface{}  //      h      (      )。
    func Push(h Interface, x interface{})  //  h     x,        。
    func Remove(h Interface, i int) interface{}  //      i   ,        。

    container / heap 용도
    1. int slice 타 입의 작은 뿌리 더미
    // This example demonstrates an integer heap built using the heap interface.
    package main
    
    import (
        "container/heap"
        "fmt"
    )
    
    // An IntHeap is a min-heap of ints.
    type IntHeap []int
    
    func (h IntHeap) Len() int           { return len(h) }
    func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } //      >    
    func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
    
    func (h *IntHeap) Push(x interface{}) {
        // Push and Pop use pointer receivers because they modify the slice's length,
        // not just its contents.
        *h = append(*h, x.(int))
    }
    
    func (h *IntHeap) Pop() interface{} {
        old := *h
        n := len(old)
        x := old[n-1]
        *h = old[0 : n-1]
        return x
    }
    
    // This example inserts several ints into an IntHeap, checks the minimum,
    // and removes them in order of priority.
    func main() {
        h := &IntHeap{2, 1, 5}
        heap.Init(h)
        heap.Push(h, 3)
        fmt.Printf("minimum: %d
    ", (*h)[0]) for h.Len() > 0 { fmt.Printf("%d ", heap.Pop(h)) } }

    2. 우선 순위 대기 열 구현 (중요: k8s 우선 순위 대기 열)
    // This example demonstrates a priority queue built using the heap interface.
    package main
    
    import (
        "container/heap"
        "fmt"
    )
    
    // An Item is something we manage in a priority queue.
    type Item struct {
        value    string // The value of the item; arbitrary.
        priority int    // The priority of the item in the queue.
        // The index is needed by update and is maintained by the heap.Interface methods.
        index int // The index of the item in the heap.
    }
    
    // A PriorityQueue implements heap.Interface and holds Items.
    type PriorityQueue []*Item
    
    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(x interface{}) {
        n := len(*pq)
        item := x.(*Item)
        item.index = n
        *pq = append(*pq, item)
    }
    
    func (pq *PriorityQueue) Pop() interface{} {
        old := *pq
        n := len(old)
        item := old[n-1]
        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 string, priority int) {
        item.value = value
        item.priority = priority
        heap.Fix(pq, item.index)
    }
    
    // This example creates a PriorityQueue with some items, adds and manipulates an item,
    // and then removes the items in priority order.
    func main() {
        // Some items and their priorities.
        items := map[string]int{
            "banana": 3, "apple": 2, "pear": 4,
        }
    
        // Create a priority queue, put the items in it, and
        // establish the priority queue (heap) invariants.
        pq := make(PriorityQueue, len(items))
        i := 0
        for value, priority := range items {
            pq[i] = &Item{
                value:    value,
                priority: priority,
                index:    i,
            }
            i++
        }
        heap.Init(&pq)
    
        // Insert a new item and then modify its priority.
        item := &Item{
            value:    "orange",
            priority: 1,
        }
        heap.Push(&pq, item)
        pq.update(item, item.value, 5)
    
        // Take the items out; they arrive in decreasing priority order.
        for pq.Len() > 0 {
            item := heap.Pop(&pq).(*Item)
            fmt.Printf("%.2d:%s ", item.priority, item.value)
        }
    }

    3. 최소 K 개수 또는 최대 K 개 수 를 처리 하고 대량의 데 이 터 를 처리 합 니 다.
  • k 개 수 를 읽 고 크기 가 k 인 큰 뿌리 더미 구축
  • 남 은 데 이 터 를 순서대로 읽 고 현재 데 이 터 는 큰 뿌리 더미 의 지붕 데이터 보다 작 으 며 큰 뿌리 더미 의 특성 을 만족 시 키 도록 교체 하고 조정 합 니 다
  • .
  • 현재 데이터 가 쌓 인 데이터 보다 크 면 이 수 를 버 립 니 다
  • 주로 더미 의 초기 화, 정렬, 조정, 그리고 더미 의 응용 장면 을 파악 할 수 있다.

    좋은 웹페이지 즐겨찾기