解题思路

  1. 插入操作(push)
    • 将新元素添加到数组末尾
    • 执行上浮操作，直到满足堆的性质
    • 上浮：与父节点比较，如果大于父节点则交换
  2. 获取堆顶(top)
    • 如果堆为空，输出"empty"
    • 否则输出数组第一个元素
  3. 删除堆顶(pop)
    • 如果堆为空，输出"empty"
    • 否则先输出堆顶元素
    • 将最后一个元素移到堆顶
    • 执行下沉操作，直到满足堆的性质
    • 下沉：与较大的子节点比较，如果小于子节点则交换

代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class MaxHeap {
private:
    vector<int> heap;
    
    void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] < heap[index]) {
                swap(heap[parent], heap[index]);
                index = parent;
            } else {
                break;
            }
        }
    }
    
    void heapifyDown(int index) {
        int size = heap.size();
        while (true) {
            int largest = index;
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            
            if (left < size && heap[left] > heap[largest]) {
                largest = left;
            }
            if (right < size && heap[right] > heap[largest]) {
                largest = right;
            }
            
            if (largest == index) {
                break;
            }
            
            swap(heap[index], heap[largest]);
            index = largest;
        }
    }
    
public:
    void push(int x) {
        heap.push_back(x);
        heapifyUp(heap.size() - 1);
    }
    
    void pop() {
        if (heap.empty()) {
            cout << "empty" << endl;
            return;
        }
        cout << heap[0] << endl;
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) {
            heapifyDown(0);
        }
    }
    
    void top() {
        if (heap.empty()) {
            cout << "empty" << endl;
        } else {
            cout << heap[0] << endl;
        }
    }
};

int main() {
    int n;
    cin >> n;
    
    MaxHeap heap;
    string op;
    int x;
    
    while (n--) {
        cin >> op;
        if (op == "push") {
            cin >> x;
            heap.push(x);
        } else if (op == "pop") {
            heap.pop();
        } else if (op == "top") {
            heap.top();
        }
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static class MaxHeap {
        private ArrayList<Integer> heap;
        
        public MaxHeap() {
            heap = new ArrayList<>();
        }
        
        private void heapifyUp(int index) {
            while (index > 0) {
                int parent = (index - 1) / 2;
                if (heap.get(parent) < heap.get(index)) {
                    Collections.swap(heap, parent, index);
                    index = parent;
                } else {
                    break;
                }
            }
        }
        
        private void heapifyDown(int index) {
            int size = heap.size();
            while (true) {
                int largest = index;
                int left = 2 * index + 1;
                int right = 2 * index + 2;
                
                if (left < size && heap.get(left) > heap.get(largest)) {
                    largest = left;
                }
                if (right < size && heap.get(right) > heap.get(largest)) {
                    largest = right;
                }
                
                if (largest == index) {
                    break;
                }
                
                Collections.swap(heap, index, largest);
                index = largest;
            }
        }
        
        public void push(int x) {
            heap.add(x);
            heapifyUp(heap.size() - 1);
        }
        
        public void pop() {
            if (heap.isEmpty()) {
                System.out.println("empty");
                return;
            }
            System.out.println(heap.get(0));
            heap.set(0, heap.get(heap.size() - 1));
            heap.remove(heap.size() - 1);
            if (!heap.isEmpty()) {
                heapifyDown(0);
            }
        }
        
        public void top() {
            if (heap.isEmpty()) {
                System.out.println("empty");
            } else {
                System.out.println(heap.get(0));
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        MaxHeap heap = new MaxHeap();
        
        while (n-- > 0) {
            String op = sc.next();
            if (op.equals("push")) {
                int x = sc.nextInt();
                heap.push(x);
            } else if (op.equals("pop")) {
                heap.pop();
            } else if (op.equals("top")) {
                heap.top();
            }
        }
    }
}

class MaxHeap:
    def __init__(self):
        self.heap = []
        
    def heapify_up(self, index):
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[parent] < self.heap[index]:
                self.heap[parent], self.heap[index] = self.heap[index], self.heap[parent]
                index = parent
            else:
                break
                
    def heapify_down(self, index):
        size = len(self.heap)
        while True:
            largest = index
            left = 2 * index + 1
            right = 2 * index + 2
            
            if left < size and self.heap[left] > self.heap[largest]:
                largest = left
            if right < size and self.heap[right] > self.heap[largest]:
                largest = right
                
            if largest == index:
                break
                
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            index = largest
            
    def push(self, x):
        self.heap.append(x)
        self.heapify_up(len(self.heap) - 1)
        
    def pop(self):
        if not self.heap:
            print("empty")
            return
        print(self.heap[0])
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        if self.heap:
            self.heapify_down(0)
            
    def top(self):
        if not self.heap:
            print("empty")
        else:
            print(self.heap[0])

n = int(input())
heap = MaxHeap()

for _ in range(n):
    op = input().split()
    if op[0] == "push":
        heap.push(int(op[1]))
    elif op[0] == "pop":
        heap.pop()
    elif op[0] == "top":
        heap.top()

这三个实现都包含了以下核心功能：

  1. heapify_up：向上调整堆
  2. heapify_down：向下调整堆
  3. push：插入元素
  4. pop：删除并返回堆顶元素
  5. top：查看堆顶元素

算法及复杂度分析

  • 算法:堆，插入，删除，获取堆顶

  • 时间复杂度：

    • push：
    • pop：
    • top：

  • 空间复杂度：，其中 是堆中元素的数量。