func TestPush(t *testing.T) {
	h := &uint64Heap{}
	heap.Init(h)

	e := elem{val: 5}
	heap.Push(h, e)
	e.val = 3
	heap.Push(h, e)
	e.val = 4
	heap.Push(h, e)

	require.Equal(t, h.Len(), 3)
	require.EqualValues(t, (*h)[0].val, 3)

	e.val = 10
	(*h)[0] = e
	heap.Fix(h, 0)
	require.EqualValues(t, (*h)[0].val, 4)

	e.val = 11
	(*h)[0] = e
	heap.Fix(h, 0)
	require.EqualValues(t, (*h)[0].val, 5)

	e = heap.Pop(h).(elem)
	require.EqualValues(t, e.val, 5)

	e = heap.Pop(h).(elem)
	require.EqualValues(t, e.val, 10)

	e = heap.Pop(h).(elem)
	require.EqualValues(t, e.val, 11)

	require.Equal(t, h.Len(), 0)
}

func main() {
	in, _ := os.Open("10954.in")
	defer in.Close()
	out, _ := os.Create("10954.out")
	defer out.Close()

	var n, num int
	for {
		if fmt.Fscanf(in, "%d", &n); n == 0 {
			break
		}
		pq := make(priorityQueue, n)
		for i := range pq {
			fmt.Fscanf(in, "%d", &num)
			pq[i] = &item{num}
		}
		heap.Init(&pq)
		total := 0
		for pq.Len() > 1 {
			n1 := heap.Pop(&pq).(*item)
			n2 := heap.Pop(&pq).(*item)
			total += n1.value + n2.value
			heap.Push(&pq, &item{n1.value + n2.value})
		}
		fmt.Fprintln(out, total)
	}
}

func TestQueue(t *testing.T) {
	q := NewImageCache()
	heap.Push(q, NewCacheItem("item1", nil))
	time.Sleep(time.Duration(1) * time.Millisecond)
	heap.Push(q, NewCacheItem("item2", nil))
	time.Sleep(time.Duration(1) * time.Millisecond)
	heap.Push(q, NewCacheItem("item3", nil))
	time.Sleep(time.Duration(1) * time.Millisecond)
	heap.Push(q, NewCacheItem("item4", nil))
	time.Sleep(time.Duration(1) * time.Millisecond)
	t.Log(q.GetPaths())

	q.Update("item1")
	t.Log(q.GetPaths())

	t.Log(q.Top().path)
	heap.Pop(q)
	t.Log(q.GetPaths())

	t.Log(q.Top().path)
	heap.Pop(q)
	t.Log(q.GetPaths())

	t.Log(q.Top().path)
	heap.Pop(q)
	t.Log(q.GetPaths())
}

// Retorna a arvore
func Harvest(freqMap map[string]int) *tree.Node {
	// Primeiro a gente cria a nossa priorityqueue a partir do dicionario de frequencias
	hh := huffmanHeap.New(freqMap)

	for {
		// Caso a heap contenha um unico elemento retornamos ela
		if hh.Len() == 1 {
			return heap.Pop(&hh).(*huffmanHeap.Item).Node
		}

		// Caso contrario pegamos os dois elementos do topo
		r, ok1 := heap.Pop(&hh).(*huffmanHeap.Item)
		l, ok2 := heap.Pop(&hh).(*huffmanHeap.Item)
		if !ok1 || !ok2 {
			panic(errors.New("Element was not of type huffmanHeap.Item"))
		}

		//E criamos uma "arvore" intermediaria com eles
		newItem := &huffmanHeap.Item{
			Node:      tree.New("", r.Node, l.Node),
			Frequency: r.Frequency + l.Frequency,
		}
		// Adicionando em seguida ao
		heap.Push(&hh, newItem)
	}
}

// makeTreeFromNodeSlice makes a tree from a slice of huffNodes, with the
// lowest-count nodes going farthest from the root. Returns a non-nil error
// on failure, nil error otherwise. Returns the created tree. If nodes is empty,
// returns an error.
func makeTreeFromNodeSlice(nodes []*huffNode) (t *huffNode, err error) {
	if len(nodes) == 0 {
		return nil, errors.New("Too few elements!")
	}
	// We're going to put the nodes in a heap, with low-ness determined
	// by the nodes' counts.
	nh := &nodeHeap{}
	heap.Init(nh)
	for _, node := range nodes {
		heap.Push(nh, node)
	}

	// Now, we're going to do the following:
	//
	// Until there's only one node in the heap:
	// 		Remove the lowest-count two nodes
	// 		Make a new node with those two as children, whose count is the
	//			sum of its childrens' counts
	//		Add that new node to the heap
	//
	// This will create an optimally-balanced tree, based on byte counts. For
	// more information, see http://en.wikipedia.org/wiki/Huffman_coding.
	for nh.Len() > 1 {
		nodeOne := heap.Pop(nh).(*huffNode)
		nodeTwo := heap.Pop(nh).(*huffNode)
		newNode := &huffNode{char: 1,
			count: nodeOne.count + nodeTwo.count,
			left:  nodeOne,
			right: nodeTwo}
		heap.Push(nh, newNode)
	}

	// Great, now there's only one node and it's the root of the tree!
	return heap.Pop(nh).(*huffNode), nil
}

// This helper function finds the k nearest neighbours of target in items. It's
// slower than the VPTree, but its correctness is easy to verify, so we can
// test the VPTree against it.
func nearestNeighbours(target uint64, items []Item, k int) (coords []Item, distances []float64) {
	pq := &priorityQueue{}

	// Push all items onto a heap
	for _, v := range items {
		d := hamming(v.Sig, target)
		heap.Push(pq, &heapItem{v, d})
	}

	// Pop all but the k smallest items
	for pq.Len() > k {
		heap.Pop(pq)
	}

	// Extract the k smallest items and distances
	for pq.Len() > 0 {
		hi := heap.Pop(pq)
		coords = append(coords, hi.(*heapItem).Item)
		distances = append(distances, hi.(*heapItem).Dist)
	}

	// Reverse coords and distances, because we popped them from the heap
	// in large-to-small order
	for i, j := 0, len(coords)-1; i < j; i, j = i+1, j-1 {
		coords[i], coords[j] = coords[j], coords[i]
		distances[i], distances[j] = distances[j], distances[i]
	}

	return
}

func (s *S) TestEvictOldest(c *C) {
	q := make(utility.PriorityQueue, 0, 10)
	heap.Init(&q)
	var e EvictionPolicy = EvictOldest(5)

	for i := 0; i < 10; i++ {
		var item utility.Item = utility.Item{
			Value:    float64(i),
			Priority: int64(i),
		}

		heap.Push(&q, &item)
	}

	c.Check(q, HasLen, 10)

	e(&q)

	c.Check(q, HasLen, 5)

	c.Check(heap.Pop(&q), utility.ValueEquals, 4.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 3.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 2.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 1.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 0.0)
}

// DeleteDuplicates heap sorts a slice and returns a new slice with duplicate
// entries removed.
func DeleteDuplicates(theArray []int) []int {
	// Need to get a mutable copy of the heap
	heapHelper := make(HeapHelper, len(theArray))
	i := 0
	for _, value := range theArray {
		heapHelper[i] = value
		i++
	}
	heap.Init(&heapHelper)

	//  How to do this in-place?
	result := make([]int, 0)

	if len(theArray) > 0 {
		prevElement := heap.Pop(&heapHelper).(int)

		result = append(result, prevElement)

		for heapHelper.Len() > 0 {
			currentElement := heap.Pop(&heapHelper).(int)
			if currentElement != prevElement {
				result = append(result, currentElement)
				prevElement = currentElement
			}
		}
	}
	return result
}

func createTreeFromFrequencies(frequencies []uint, sizes_ []byte, ranks []byte) error {
	// Create Huffman tree of (present) symbols
	queue := make(HuffmanPriorityQueue, 0)

	for i := range ranks {
		heap.Push(&queue, &HuffmanNode{symbol: ranks[i], weight: frequencies[ranks[i]]})
	}

	for queue.Len() > 1 {
		// Extract 2 minimum nodes, merge them and enqueue result
		lNode := heap.Pop(&queue).(*HuffmanNode)
		rNode := heap.Pop(&queue).(*HuffmanNode)

		// Setting the symbol is critical to resolve ties during node sorting !
		heap.Push(&queue, &HuffmanNode{weight: lNode.weight + rNode.weight, left: lNode, right: rNode, symbol: lNode.symbol})
	}

	rootNode := heap.Pop(&queue).(*HuffmanNode)
	var err error

	if len(ranks) == 1 {
		sizes_[rootNode.symbol] = byte(1)
	} else {
		err = fillSizes(rootNode, 0, sizes_)
	}

	return err
}

func findMin(n, k, a, b, c, r int) int {
	m := []int{a}
	for i := 1; i < k; i++ {
		m = append(m, (b*m[i-1]+c)%r)
	}
	o := make([]int, k)
	copy(o, m)
	sort.Ints(o)
	h := &intHeap{}
	heap.Init(h)
	var x, y int
	for i := 0; i <= k; {
		if y >= k || x < o[y] {
			heap.Push(h, x)
			x++
			i++
		} else {
			if x == o[y] {
				x++
			}
			y++
		}
	}
	for len(m)+1 < n {
		p := heap.Pop(h).(int)
		if h.notyet(m[len(m)-k]) && notagain(m[len(m)-k+1:len(m)], m[len(m)-k]) {
			heap.Push(h, m[len(m)-k])
		}
		m = append(m, p)
	}
	return heap.Pop(h).(int)
}

func TestPriorityQueue(t *testing.T) {
	pq := New()
	heap.Init(pq)
	heap.Push(pq, &Item{Value: "hello3", Priority: 3})
	heap.Push(pq, &Item{Value: "hello1", Priority: 1})
	heap.Push(pq, &Item{Value: "hello8", Priority: 8})

	assert.Equal(t, 3+1+8, pq.PrioritySum())

	item := pq.Peek()
	assert.Equal(t, "hello8", item.(*Item).Value.(string))
	item = pq.Peek()
	assert.Equal(t, "hello8", item.(*Item).Value.(string))

	item = heap.Pop(pq)
	assert.Equal(t, "hello8", item.(*Item).Value.(string))
	assert.Equal(t, 3+1, pq.PrioritySum())

	item = heap.Pop(pq)
	assert.Equal(t, "hello3", item.(*Item).Value.(string))

	item = heap.Pop(pq)
	assert.Equal(t, "hello1", item.(*Item).Value.(string))

	assert.Equal(t, 0, pq.Len())
}

func TestJobHeap(t *testing.T) {
	jobs := &JobHeap{}
	heap.Init(jobs)

	job1 := Job{Description: "job 1", Created: time.Now()}
	job2 := Job{Description: "job 2", Created: time.Now()} //, Ctrl: JobControl{JobPriority: 100}}
	job3 := Job{Description: "job 3", Created: time.Now()} //, Ctrl: JobControl{JobPriority: 104}}

	heap.Push(jobs, &job2)
	heap.Push(jobs, &job3)
	heap.Push(jobs, &job1)

	for _, job := range *jobs {
		fmt.Println(job)
	}

	fmt.Println("===")
	fmt.Println(jobs.Peek())

	fmt.Println("---")
	ret1 := heap.Pop(jobs)
	ret2 := heap.Pop(jobs)
	ret3 := heap.Pop(jobs)

	fmt.Println(ret1)
	fmt.Println(ret2)
	fmt.Println(ret3)

}

func TestEventQueue(t *testing.T) {
	queue := make(EventQueue, 0, 4)
	heap.Push(&queue, &Event{Y: 5})
	heap.Push(&queue, &Event{Y: 3})
	heap.Push(&queue, &Event{Y: 7})
	heap.Push(&queue, &Event{Y: 1})

	var e *Event
	e = heap.Pop(&queue).(*Event)
	if e.Y != 7 {
		t.Fatalf("Wanted priority 7, got %v", e.Y)
	}
	e = heap.Pop(&queue).(*Event)
	if e.Y != 5 {
		t.Fatalf("Wanted priority 5, got %v", e.Y)
	}
	e = heap.Pop(&queue).(*Event)
	if e.Y != 3 {
		t.Fatalf("Wanted priority 3, got %v", e.Y)
	}
	e = heap.Pop(&queue).(*Event)
	if e.Y != 1 {
		t.Fatalf("Wanted priority 1, got %v", e.Y)
	}
}

func addMinPathLeft(graph *m.Graph) {
	dp := &m.DijkstraPrio{}
	heap.Init(dp)
	visited := make(map[*m.Node]bool)
	endNode := graph.EndNode()
	endNode.SetMinPathLeft(0)
	visited[endNode] = true
	for _, edge := range endNode.ToEdges() {
		node := edge.From()
		node.SetMinPathLeft(edge.FastestTime())
		heap.Push(dp, node)
	}
	if dp.Len() > 0 {
		for node := heap.Pop(dp).(*m.Node); dp.Len() > 0; node = heap.Pop(dp).(*m.Node) {
			visited[node] = true
			for _, edge := range node.ToEdges() {
				innerNode := edge.From()
				if !visited[innerNode] {
					innerNode.SetMinPathLeft(edge.FastestTime() + node.MinPathLeft())
					heap.Push(dp, innerNode)
				}
			}
		}
	}
}

// ConsiderWeighted lets the sample inspect a new value with a positive given
// weight. A weight of one corresponds to the unweighted reservoir sampling
// algorithm. A nonpositive weight will lead to the item being rejected without
// having been observed. To avoid numerical instabilities, it is advisable to
// stay away from zero and infinity, or more generally from regions in which
// computing x**1/weight may be ill-behaved.
func (rs *WeightedReservoirSample) ConsiderWeighted(value interface{}, weight float64) {
	if weight <= 0 {
		glog.Warningf("reservoir sample received non-positive weight %f", weight)
		return
	}
	h := rs.Heap
	wv := WeightedValue{
		Value: value,
		key:   rs.makeKey(weight),
	}
	if h.Len() < rs.size {
		heap.Push(h, wv)
		if rs.threshold == 0 || wv.key < rs.threshold {
			rs.threshold = wv.key
		}
		return
	}

	if wv.key > rs.threshold {
		// Remove the element with threshold key.
		heap.Pop(h)
		// Add in the new element (which has a higher key).
		heap.Push(h, wv)
		// Update the threshold to reflect the new threshold.
		twv := heap.Pop(h).(WeightedValue)
		rs.threshold = twv.key
		heap.Push(h, twv)
	}
}

func DestructiveUnionSloppy(polygons *[]*Polygon, vertexMergeRadius s1.Angle) *Polygon {
	// Create a priority queue of polygons in order of number of vertices.
	// Repeatedly union the two smallest polygons and add the result to the
	// queue until we have a single polygon to return.
	pq := make(IntPolygonQueue, len(*polygons))
	for i := 0; i < len(*polygons); i++ {
		pq[i] = &IntPolygonPair{
			size: (*polygons)[i].numVertices,
			poly: (*polygons)[i],
		}
	}
	heap.Init(&pq)
	*polygons = []*Polygon{}
	for pq.Len() > 1 {
		// Pop two simplest polygons from queue.
		a := heap.Pop(&pq).(*IntPolygonPair)
		b := heap.Pop(&pq).(*IntPolygonPair)
		// Union and add result back to queue.
		var c Polygon
		c.InitToUnionSloppy(a.poly, b.poly, vertexMergeRadius)
		heap.Push(&pq, &IntPolygonPair{
			size: a.size + b.size,
			poly: &c,
		})
	}
	if pq.Len() == 0 {
		return &Polygon{}
	}
	return heap.Pop(&pq).(*IntPolygonPair).poly
}

// NewTree creates a huffman tree and gets the codes for the symbol
// frequencies given.
func NewTree(freqs rle2.Frequencies) *Tree {
	tree := &Tree{Codes: make([]*Code, len(freqs))}

	var queue NodeQueue
	for i, f := range freqs {
		queue = append(queue, &Node{Value: uint16(i), Frequency: f})
	}
	heap.Init(&queue)

	// As long as we have multiple nodes, remove the two lowest frequency
	// symbols and create a new node with them as children.
	for queue.Len() > 1 {
		left := heap.Pop(&queue).(*Node)
		right := heap.Pop(&queue).(*Node)

		heap.Push(&queue, &Node{
			Left:      left,
			Right:     right,
			Frequency: left.Frequency + right.Frequency,
		})
	}

	tree.root = heap.Pop(&queue).(*Node)
	tree.getCodes(tree.root, 0, 0)
	return tree
}

// notifyConfs examines the current confirmation heap, sending off any
// notifications which have been triggered by the connection of a new block at
// newBlockHeight.
func (b *BtcdNotifier) notifyConfs(newBlockHeight int32) {
	// If the heap is empty, we have nothing to do.
	if b.confHeap.Len() == 0 {
		return
	}

	// Traverse our confirmation heap. The heap is a
	// min-heap, so the confirmation notification which requires
	// the smallest block-height will always be at the top
	// of the heap. If a confirmation notification is eligible
	// for triggering, then fire it off, and check if another
	// is eligible until there are no more eligible entries.
	nextConf := heap.Pop(b.confHeap).(*confEntry)
	for nextConf.triggerHeight <= uint32(newBlockHeight) {
		nextConf.finConf <- newBlockHeight

		if b.confHeap.Len() == 0 {
			return
		}

		nextConf = heap.Pop(b.confHeap).(*confEntry)
	}

	heap.Push(b.confHeap, nextConf)
}

func TestScanCursors(t *testing.T) {
	s := ScanCursors{}
	heap.Init(&s)
	heap.Push(&s, &testScanCursor{
		key: "b",
	})
	heap.Push(&s, &testScanCursor{
		key: "a",
	})
	heap.Push(&s, &testScanCursor{
		key: "c",
	})
	a := heap.Pop(&s).(*testScanCursor)
	if a.key != "a" {
		t.Errorf("expected a")
	}
	b := heap.Pop(&s).(*testScanCursor)
	if b.key != "b" {
		t.Errorf("expected b")
	}
	c := heap.Pop(&s).(*testScanCursor)
	if c.key != "c" {
		t.Errorf("expected c")
	}
}

// Run is the block's main loop. Here we listen on the different channels we set up.
func (b *Queue) Run() {
	pq := &PriorityQueue{}
	heap.Init(pq)
	for {
		select {
		case <-b.quit:
			// quit the block
			return
		case msg := <-b.inPush:
			queueMessage := &PQMessage{
				val: msg,
				t:   time.Now(),
			}
			heap.Push(pq, queueMessage)
		case <-b.inPop:
			if len(*pq) == 0 {
				continue
			}
			msg := heap.Pop(pq).(*PQMessage).val
			b.out <- msg
		case MsgChan := <-b.queryPop:
			var msg interface{}
			if len(*pq) > 0 {
				msg = heap.Pop(pq).(*PQMessage).val
			}
			MsgChan <- msg
		case MsgChan := <-b.queryPeek:
			var msg interface{}
			if len(*pq) > 0 {
				msg = pq.Peek().(*PQMessage).val
			}
			MsgChan <- msg
		}
	}
}