副队长的堆

本题考察堆的构建和实现。这题的实现比较底层，相比起洛谷或其他地方的堆模板题，该题更深入了优先队列的底层，提供直接访问堆内部成员的要求，灵活性更高

思路

模拟实现堆

C 语言朴素实现

#include <stdio.h>
#include <stdbool.h>

typedef unsigned long long u64;

u64 heap[1000005];
u64 size = 0;

void swap(u64 *a, u64 *b) {
    u64 t = *a;
    *a = *b;
    *b = t;
}

void down(u64 i) {
    u64 parent = i;
    u64 child = parent << 1 | 1;
    while (child < size) {
        if (child + 1 < size && heap[child] > heap[child + 1])
            child++;
        if (heap[parent] <= heap[child])
            return;
        swap(&heap[parent], &heap[child]);
        parent = child;
        child = parent << 1 | 1;
    }
}

void up(u64 i) {
    u64 child = i;
    u64 parent = (child - 1) >> 1;
    while (child > 0 && heap[parent] > heap[child]) {
        swap(&heap[parent], &heap[child]);
        child = parent;
        parent = (child - 1) >> 1;
    }
}

void pop() {
    if (size == 0)
        return;
    swap(&heap[0], &heap[--size]);
    down(0);
}

void push(u64 val) {
    heap[size] = val;
    up(size++);
}

bool empty() {
    return size == 0;
}

int main() {
    u64 op;
    while (scanf("%llu", &op), op != 0) {
        if (op == 1) {
            if (empty())
                printf("-1\n");
            else {
                for (u64 i = 0; i < size; i++)
                    printf("%llu ", heap[i]);
                printf("\n");
            }
        } else if (op == 2) {
            u64 val;
            scanf("%llu", &val);
            push(val);
        } else if (op == 3) {
            if (empty())
                printf("-1\n");
            else
                printf("%llu\n", heap[0]);
        } else if (op == 4) {
            if (!empty())
                pop();
        }
    }
    return 0;
}

C++ STL实现

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<uint64_t> heap;
    int op;
    while (cin >> op and op) {
        if (op == 1) {
            if (heap.empty())
                cout << -1;
            else
                for (auto &&i: heap)
                    cout << i << ' ';
            cout << endl;
        } else if (op == 2) {
            uint64_t v;
            cin >> v;
            heap.emplace_back(v);
            // C++20之前
            // push_heap(heap.begin(), heap.end(), greater<int64_t>());
            ranges::push_heap(heap, greater<>());
        } else if (op == 3) {
            if (heap.empty())
                cout << -1 << endl;
            else
                cout << heap.front() << endl;
        } else if (not heap.empty()) {
            // C++20之前
            // pop_heap(heap.begin(), heap.end(), greater<int64_t>());
            ranges::pop_heap(heap, greater<>());
            heap.pop_back();
        }
    }
    return 0;
}

Python 实现

from sys import stdin
from heapq import *
input = stdin.readline
heap = []
while True:
    line = list(map(int, input().split()))
    op = line[0]
    if op == 0:
        break
    if op == 1:
        if len(heap) == 0:
            print(-1)
        else:
            for i in heap:
                print(i, end=" ")
            print()
    elif op == 2:
        heappush(heap, line[1])
    elif op == 3:
        if len(heap) == 0:
            print(-1)
        else:
            print(heap[0])
    elif op == 4:
        if len(heap) != 0:
            heappop(heap);

Java 实现

本来想写的，但是这语言又臭又长又难用的，就去掉了。实现思路参考纯 C 语言实现