Priority Queue

pick a language to open the code

import heapq


def push(queue, value):
    heapq.heappush(queue, -value)


def pop(queue):
    return -heapq.heappop(queue)


def peek(queue):
    return -queue[0]


def run(stream):
    queue = []
    served = []
    for value in stream:
        if value > 0:
            push(queue, value)
        elif queue:
            served.append(pop(queue))
    return served

class PriorityQueue {
  heap = [];
  peek() {
    return this.heap[0];
  }
  push(value) {
    const heap = this.heap;
    heap.push(value);
    let at = heap.length - 1;
    while (at > 0) {
      const parent = (at - 1) >> 1;
      if (heap[parent] >= heap[at]) return;
      [heap[parent], heap[at]] = [heap[at], heap[parent]];
      at = parent;
    }
  }
  pop() {
    const heap = this.heap;
    const top = heap[0];
    const last = heap.pop();
    if (heap.length === 0) return top;
    heap[0] = last;
    let at = 0;
    for (;;) {
      let child = 2 * at + 1;
      if (child >= heap.length) return top;
      if (child + 1 < heap.length && heap[child] < heap[child + 1]) child++;
      if (heap[at] >= heap[child]) return top;
      [heap[at], heap[child]] = [heap[child], heap[at]];
      at = child;
    }
  }
}

function run(stream) {
  const queue = new PriorityQueue();
  const served = [];
  for (const value of stream) {
    if (value > 0) queue.push(value);
    else if (queue.heap.length > 0) served.push(queue.pop());
  }
  return served;
}

typedef struct {
    int *slot;
    int size;
} Queue;

void pq_push(Queue *q, int value) {
    int at = q->size++;
    q->slot[at] = value;
    while (at > 0) {
        int parent = (at - 1) / 2;
        int keep;
        if (q->slot[parent] >= q->slot[at]) return;
        keep = q->slot[parent];
        q->slot[parent] = q->slot[at];
        q->slot[at] = keep;
        at = parent;
    }
}

int pq_peek(const Queue *q) {
    return q->slot[0];
}

int pq_pop(Queue *q) {
    int top = q->slot[0];
    int at = 0;
    q->slot[0] = q->slot[--q->size];
    for (;;) {
        int child = 2 * at + 1;
        int keep;
        if (child >= q->size) return top;
        if (child + 1 < q->size && q->slot[child] < q->slot[child + 1]) child++;
        if (q->slot[at] >= q->slot[child]) return top;
        keep = q->slot[at];
        q->slot[at] = q->slot[child];
        q->slot[child] = keep;
        at = child;
    }
}

int pq_peek(const std::priority_queue<int> &queue) {
    return queue.top();
}

int pq_pop(std::priority_queue<int> &queue) {
    int top = queue.top();
    queue.pop();
    return top;
}

std::vector<int> run(const std::vector<int> &stream) {
    std::priority_queue<int> queue;
    std::vector<int> served;
    for (int value : stream) {
        if (value > 0) {
            queue.push(value);
        } else if (!queue.empty()) {
            served.push_back(pq_pop(queue));
        }
    }
    return served;
}

static int Peek(PriorityQueue<int, int> queue) {
    return queue.Peek();
}

static int Pop(PriorityQueue<int, int> queue) {
    return queue.Dequeue();
}

static int[] Run(int[] stream) {
    var queue = new PriorityQueue<int, int>();
    var served = new List<int>();
    foreach (int value in stream) {
        if (value > 0) {
            queue.Enqueue(value, -value);
        } else if (queue.Count > 0) {
            served.Add(queue.Dequeue());
        }
    }
    return served.ToArray();
}

static int peek(PriorityQueue<Integer> queue) {
    return queue.peek();
}

static int pop(PriorityQueue<Integer> queue) {
    return queue.poll();
}

static int[] run(int[] stream) {
    PriorityQueue<Integer> queue =
        new PriorityQueue<>(Comparator.reverseOrder());
    List<Integer> served = new ArrayList<>();
    for (int value : stream) {
        if (value > 0) {
            queue.add(value);
        } else if (!queue.isEmpty()) {
            served.add(queue.poll());
        }
    }
    int[] out = new int[served.size()];
    for (int i = 0; i < out.length; i++) out[i] = served.get(i);
    return out;
}