Что не так с методом Pop моей Приоритетной очереди? - PullRequest
Новая
       19

Что не так с методом Pop моей Приоритетной очереди?

2 голосов
/ 12 августа 2010

Основываясь на демонстрации балансировки нагрузки Роба Пайка , я реализовал собственную очередь приоритетов, но мой метод Pop не подходит, кто-нибудь может сказать мне, что не так? 

package main

import (
    "fmt"
    "container/heap"
)

type ClassRecord struct {
    name  string
    grade int
}

type RecordHeap []*ClassRecord

func (p RecordHeap) Len() int { return len(p) }

func (p RecordHeap) Less(i, j int) bool {
    return p[i].grade < p[j].grade
}

func (p *RecordHeap) Swap(i, j int) {
    a := *p
    a[i], a[j] = a[j], a[i]
}

func (p *RecordHeap) Push(x interface{}) {
    a := *p
    n := len(a)
    a = a[0 : n+1]
    r := x.(*ClassRecord)
    a[n] = r
    *p = a
}

func (p *RecordHeap) Pop() interface{} {
    a := *p
    *p = a[0 : len(a)-1]
    r := a[len(a)-1]
    return r
}

func main() {
    a := make([]ClassRecord, 6)
    a[0] = ClassRecord{"John", 80}
    a[1] = ClassRecord{"Dan", 85}
    a[2] = ClassRecord{"Aron", 90}
    a[3] = ClassRecord{"Mark", 65}
    a[4] = ClassRecord{"Rob", 99}
    a[5] = ClassRecord{"Brian", 78}
    h := make(RecordHeap, 0, 100)
    for _, c := range a {
        fmt.Println(c)
        heap.Push(&h, &c)
        fmt.Println("Push: heap has", h.Len(), "items")
    }
    for i, x := 0, heap.Pop(&h).(*ClassRecord); i < 10 && x != nil; i++ {
        fmt.Println("Pop: heap has", h.Len(), "items")
        fmt.Println(*x)
    }
}

РЕДАКТИРОВАТЬ: помимо способа, указанного cthom06, еще один способ исправить это - создать массив указателей следующим образом: 

a := make([]*ClassRecord, 6)
a[0] = &ClassRecord{"John", 80}
a[1] = &ClassRecord{"Dan", 85}
......

1 Ответ

1 голос
/ 12 августа 2010

РЕДАКТИРОВАТЬ:

О, я должен был увидеть это сразу. 

heap.Push(&h, &c)

Вы нажимаете адрес c, который используется повторно на каждой итерации диапазона.Каждая запись в куче является указателем на одну и ту же область в памяти, которая в итоге оказывается Брайаном.Я не уверен, является ли это предполагаемым поведением или ошибкой компилятора, но 

t := c
heap.Push(&h, &t)

работает вокруг этого.

Также: Ваш цикл for неправильный.1013 * должен это исправить.

...