package main

import "errors"

type PQueue struct {
  id int
  array []int
}

func (q *PQueue) isEmpty() bool {
  return q.array == nil || len(q.array) < 2
}



func (q *PQueue) push( v int) {
  if q.array == nil {
    q.array = make([]int, 1)
  }
  q.array = append(q.array, v)

  for i := len(q.array) - 1 ; i > 1 ; i = i >> 1 {
    if q.array[i] > q.array[i>>1] {
      q.array[i], q.array[i>>1] = q.array[i>>1], q.array[i]
    } else {
      break
    }
  }

  return 
}

func (q *PQueue) pop() (v int,err error) {
  if q.isEmpty() {
    return -1, errors.New("PQeueue empty")
  }

  v = q.array[1]

  q.array[1] = q.array[len(q.array)-1]
  q.array = q.array[:len(q.array)-1]


  ind := 2
  for i := 1 ; i*2 < len(q.array) ; i = ind {
    if i << 1 + 1 < len(q.array) {
      if q.array[i<<1+1] > q.array[i<<1] {
        ind=i<<1+1
      } else {
        ind=i<<1
      }
    }

    if q.array[ind] > q.array[i] {
      q.array[ind], q.array[i] = q.array[i], q.array[ind]
    } else {
      break
    }
  }


  return 
}