Envío 6363

Código

package main

import (
    "fmt"
    "os"
    "bufio"
    "strconv"
    "strings"
)

type Node struct {
    S string;
    P int;
}

type Heap struct {
    Tree []Node;
}

func NewHeap() Heap {
    arr := make([]Node, 0)
    return Heap {
        Tree: arr,
    }
}

func Left(i int) int {
    return i >> 1 + 1
}

func Right(i int) int {
    return i >> 1 + 2
}

func Parent(i int) int {
    return (i - 1) >> 1
}

func Cmp(n1, n2 Node) int {
    if n1.P < n2.P {
        return -1
    } else if n1.P > n2.P {
        return 1
    } else {
        return strings.Compare(n1.S, n2.S)
    }
}

func (h *Heap) HeapifyDown(i int) {
    l := Left(i)
    r := Right(i)
    smallest := i
    
    if l < len(h.Tree) && Cmp(h.Tree[l], h.Tree[i]) < 0 {
        smallest = l
    }
    if r < len(h.Tree) && Cmp(h.Tree[r], h.Tree[smallest]) < 0 {
        smallest = r
    }
    if smallest != i {
        h.Tree[i], h.Tree[smallest] = h.Tree[smallest], h.Tree[i]
        h.HeapifyDown(smallest)
    }
}

func (h *Heap) Pop() Node {
    var res Node
    last := len(h.Tree) - 1
    h.Tree[last], h.Tree[0] = h.Tree[0], h.Tree[last]
    // TODO CHECK!
    h.Tree, res = h.Tree[0:last], h.Tree[last]
    h.HeapifyDown(0)
    return res
}

func (h *Heap) HeapifyUp(i int) {
    for i != 0 {
        p := Parent(i)
        if Cmp(h.Tree[p], h.Tree[i]) <= 0 {
            break
        }
        h.Tree[p], h.Tree[i] = h.Tree[i], h.Tree[p]
        i = p
    }
}

func (h *Heap) Add(elem Node) {
    h.Tree = append(h.Tree, elem)
    h.HeapifyUp(len(h.Tree) - 1)
}

func (h *Heap) Peek() Node{
    return h.Tree[0]
}

func main() {
    var p int
    var s, line, dummy string
    sc := bufio.NewScanner(os.Stdin)
    
    sc.Scan()
    ops, _ := strconv.Atoi(sc.Text())

    h := NewHeap()

    for o := 0; o < ops; o += 1 {
        sc.Scan()
        line = sc.Text() 
        if line[0] == 'I' {
            fmt.Sscanf(line, "%s %s %d", &dummy, &s, &p)
            n := Node{
                S: s,
                P: -p,
            }
            h.Add(n)
        } else if line[0] == 'G' {
            fmt.Println(h.Peek().S)

        } else {
            h.Pop()
        }
    }
}