java大根堆实现

在Java中实现一个大根堆（Max Heap），通常我们会定义一个自定义的类来表示堆结构，并实现相关的插入（insert）、删除最大元素（removeMax）以及调整堆（heapify）等方法。以下是一个简单的示例来说明如何实现一个大根堆：

首先，我们定义一个MaxHeap类：

public class MaxHeap {
    private int[] heapArray;
    private int size;
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heapArray = new int[capacity];
    }

    // 插入元素
    public void insert(int value) {
        if (size == capacity) {
            throw new IllegalStateException("Heap is full");
        }
        heapArray[size] = value;
        siftUp(size);
        size++;
    }

    // 删除并返回最大元素
    public int removeMax() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = heapArray[0];
        heapArray[0] = heapArray[--size];
        heapArray[size] = 0; // Optional: help GC
        siftDown(0);
        return max;
    }

    // 上浮操作，保持堆的性质
    private void siftUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heapArray[index] > heapArray[parentIndex]) {
                swap(index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 下沉操作，保持堆的性质
    private void siftDown(int index) {
        int leftChildIndex, rightChildIndex, largestIndex;
        while (true) {
            leftChildIndex = 2 * index + 1;
            rightChildIndex = 2 * index + 2;
            largestIndex = index;

            if (leftChildIndex < size && heapArray[leftChildIndex] > heapArray[largestIndex]) {
                largestIndex = leftChildIndex;
            }

            if (rightChildIndex < size && heapArray[rightChildIndex] > heapArray[largestIndex]) {
                largestIndex = rightChildIndex;
            }

            if (largestIndex == index) {
                break;
            }

            swap(index, largestIndex);
            index = largestIndex;
        }
    }

    // 交换两个元素
    private void swap(int i, int j) {
        int temp = heapArray[i];
        heapArray[i] = heapArray[j];
        heapArray[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

这个类定义了一个大根堆，其中包含了初始化堆、插入元素、删除最大元素、上浮和下沉等基本操作。insert方法用于向堆中添加元素，并通过siftUp方法维护堆的性质；removeMax方法移除并返回堆顶的最大元素，然后通过siftDown方法调整堆以保持其结构。注意，这里的实现是基于数组的，且为了简单起见，没有实现扩容逻辑，当堆满时会抛出异常。在实际应用中，你可能需要根据需求添加扩容功能。