go에서의 우선 순위 큐 구현

Question

우선 순위 큐 구현을 보았습니다. 인터페이스를 만족하는 유형 을 대기열에 넣을 수있는 일반적인 종류는입니다. 이것이 가야할 길인가요? 아니면 어떤 문제가 있습니까?

// Copyright 2012 Stefan Nilsson 
// 
// Licensed under the Apache License, Version 2.0 (the "License"); 
// you may not use this file except in compliance with the License. 
// You may obtain a copy of the License at 
// 
//  http://www.apache.org/licenses/LICENSE-2.0 
// 
// Unless required by applicable law or agreed to in writing, software 
// distributed under the License is distributed on an "AS IS" BASIS, 
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
// See the License for the specific language governing permissions and 
// limitations under the License. 

// Package prio provides a priority queue. 
// The queue can hold elements that implement the two methods of prio.Interface. 
package prio 

/* 
A type that implements prio.Interface can be inserted into a priority queue. 

The simplest use case looks like this: 

     type myInt int 

     func (x myInt) Less(y prio.Interface) bool { return x < y.(myInt) } 
     func (x myInt) Index(i int)    {} 

To use the Remove method you need to keep track of the index of elements 
in the heap, e.g. like this: 

     type myType struct { 
       value int 
       index int // index in heap 
     } 

     func (x *myType) Less(y prio.Interface) bool { return x.value < y.(*myType).value } 
     func (x *myType) Index(i int)    { x.index = i } 
*/ 
type Interface interface { 
     // Less returns whether this element should sort before element x. 
     Less(x Interface) bool 
     // Index is called by the priority queue when this element is moved to index i. 
     Index(i int) 
} 

// Queue represents a priority queue. 
// The zero value for Queue is an empty queue ready to use. 
type Queue struct { 
     h []Interface 
} 

// New returns an initialized priority queue with the given elements. 
// A call of the form New(x...) uses the underlying array of x to implement 
// the queue and hence might change the elements of x. 
// The complexity is O(n), where n = len(x). 
func New(x ...Interface) Queue { 
     q := Queue{x} 
     heapify(q.h) 
     return q 
} 

// Push pushes the element x onto the queue. 
// The complexity is O(log(n)) where n = q.Len(). 
func (q *Queue) Push(x Interface) { 
     n := len(q.h) 
     q.h = append(q.h, x) 
     up(q.h, n) // x.Index(n) is done by up. 
} 

// Pop removes a minimum element (according to Less) from the queue and returns it. 
// The complexity is O(log(n)), where n = q.Len(). 
func (q *Queue) Pop() Interface { 
     h := q.h 
     n := len(h) - 1 
     x := h[0] 
     h[0], h[n] = h[n], nil 
     h = h[:n] 
     if n > 0 { 
       down(h, 0) // h[0].Index(0) is done by down. 
     } 
     q.h = h 
     x.Index(-1) // for safety 
     return x 
} 

// Peek returns, but does not remove, a minimum element (according to Less) of the queue. 
func (q *Queue) Peek() Interface { 
     return q.h[0] 
} 

// Remove removes the element at index i from the queue and returns it. 
// The complexity is O(log(n)), where n = q.Len(). 
func (q *Queue) Remove(i int) Interface { 
     h := q.h 
     n := len(h) - 1 
     x := h[i] 
     h[i], h[n] = h[n], nil 
     h = h[:n] 
     if i < n { 
       down(h, i) // h[i].Index(i) is done by down. 
       up(h, i) 
     } 
     q.h = h 
     x.Index(-1) // for safety 
     return x 
} 

// Len returns the number of elements in the queue. 
func (q *Queue) Len() int { 
     return len(q.h) 
} 

// Establishes the heap invariant in O(n) time. 
func heapify(h []Interface) { 
     n := len(h) 
     for i := n - 1; i >= n/2; i-- { 
       h[i].Index(i) 
     } 
     for i := n/2 - 1; i >= 0; i-- { // h[i].Index(i) is done by down. 
       down(h, i) 
     } 
} 

// Moves element at position i towards top of heap to restore invariant. 
func up(h []Interface, i int) { 
     for { 
       parent := (i - 1)/2 
       if i == 0 || h[parent].Less(h[i]) { 
         h[i].Index(i) 
         break 
       } 
       h[parent], h[i] = h[i], h[parent] 
       h[i].Index(i) 
       i = parent 
     } 
} 

// Moves element at position i towards bottom of heap to restore invariant. 
func down(h []Interface, i int) { 
     for { 
       n := len(h) 
       left := 2*i + 1 
       if left >= n { 
         h[i].Index(i) 
         break 
       } 
       j := left 
       if right := left + 1; right < n && h[right].Less(h[left]) { 
         j = right 
       } 
       if h[i].Less(h[j]) { 
         h[i].Index(i) 
         break 
       } 
       h[i], h[j] = h[j], h[i] 
       h[i].Index(i) 
       i = j 
     } 
} 

Answer 1

이 패키지는 일반적으로 이동하는 방법이 아니라, 당신이 그것을 좋아하고 당신의 요구를 충족하는 경우, 그것을 사용할 수 있습니다. 나는 어떤 중요한 문제도 보지 못했다.

컨테이너/힙과 비교 한이 패키지의 개념은 컨테이너가 아닌 노드에 인터페이스를 배치하는 것입니다. 컨테이너/힙은 컨테이너를 사용하여 더 많은 유연성을 제공합니다. (컨테이너에 이미 노드가 있고 그 컨테이너가 슬라이스가 아닐 수도 있습니다. 인덱스 할 수 있어야합니다.) 반면에 컨테이너를 신경 쓰지 않는 일반적인 경우 일 수 있습니다. 패키지가 귀하를 위해 그것을 관리하게 해 주어서 기쁩니다. 이 패키지의 인덱스 관리는 컨테이너/힙에 비해 좋은 기능이지만 인덱스 관리가 필요하지 않은 경우에도 메서드 호출의 오버 헤드가 추가됩니다.

항상 상충 관계가 있습니다. 컨테이너/힙은 매우 일반적입니다. 이 패키지는 더 작은 메소드 세트 (5 대신 2)로 가져오고 맨 위에 인덱스 관리를 추가하지만 약간의 보편성과 경우에 따라서는 약간의 성능 만 희생시켜야합니다. (당신이 정말로 신경 쓰면 벤치 마크하고 싶을 것입니다. 인덱스 호출의 오버 헤드를 줄이는 다른 차이점이 있습니다.)