Java语言实现最大堆代码示例

让我为您详细讲解“Java语言实现最大堆代码示例”的完整攻略。

最大堆简介

最大堆是一种满足父节点比子节点大的堆，它通常用于对数据进行排序和查找最大值。最大堆可以通过用数组表示、从根节点开始，每次比较左右子节点的大小，决定是否交换它们来实现。

Java实现最大堆代码示例

下面是Java实现最大堆代码的示例：

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

    public MaxHeap(int maxSize) {
        heapArray = new int[maxSize];
        size = 0;
    }

    public void insert(int value) {
        if (size == heapArray.length) {
            throw new ArrayIndexOutOfBoundsException("Heap is full.");
        }

        heapArray[size] = value;
        int current = size;
        while (heapArray[current] > heapArray[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
        size++;
    }

    public int remove() {
        if(size == 0) {
            throw new NullPointerException("Heap is empty.");
        }

        int root = heapArray[0];
        heapArray[0] = heapArray[size - 1];
        size--;
        heapify(0);

        return root;
    }

    private void heapify(int pos) {
        if (isLeaf(pos)) {
            return;
        }

        int leftChild = leftChild(pos);
        int rightChild = rightChild(pos);
        int max = pos;
        if (leftChild < size && heapArray[leftChild] > heapArray[max]) {
            max = leftChild;
        }
        if (rightChild < size && heapArray[rightChild] > heapArray[max]) {
            max = rightChild;
        }
        if (max != pos) {
            swap(pos, max);
            heapify(max);
        }
    }

    private int parent(int pos) {
        return (pos - 1) / 2;
    }

    private int leftChild(int pos) {
        return 2 * pos + 1;
    }

    private int rightChild(int pos) {
        return 2 * pos + 2;
    }

    private boolean isLeaf(int pos) {
        return pos >= (size / 2) && pos < size;
    }

    private void swap(int a, int b) {
        int temp = heapArray[a];
        heapArray[a] = heapArray[b];
        heapArray[b] = temp;
    }
}

上面的代码示例中，我们创建了一个名为MaxHeap的类，它有以下方法：

• insert(int value)：向堆中插入一个值，保持堆继续满足最大堆的要求。
• remove()：移除堆中的最大值，并返回。
• heapify(int pos)：从给定位置开始重构最大堆，让堆重新满足最大堆的要求。
• parent(int pos)：返回一个节点的父节点的位置。
• leftChild(int pos)：返回一个节点的左子节点的位置。
• rightChild(int pos)：返回一个节点的右子节点的位置。
• isLeaf(int pos)：检查一个节点是否叶子节点。

示例说明

示例一

以下是一个简单的使用示例：

public class Main {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(15);
        maxHeap.insert(5);
        maxHeap.insert(3);
        maxHeap.insert(17);
        maxHeap.insert(10);
        maxHeap.insert(84);
        maxHeap.insert(19);
        maxHeap.insert(6);
        maxHeap.insert(22);
        maxHeap.insert(9);

        System.out.print("Heap: ");
        for(int i=0; i<9; i++) {
            System.out.print(maxHeap.remove()+ " ");
        }
    }
}

输出结果如下：

Heap: 84 22 19 17 10 9 6 5 3

在示例中，我们先实例化一个MaxHeap对象，然后向其中插入了一些数字，然后从堆中移除最大值，并打印出堆成员的剩余值。

示例二

以下是一个更高级的示例，它使用了自定义类作为堆的元素：

public class StudentHeap {
    private Student[] heapArray;
    private int size;

    public StudentHeap(int maxSize) {
        heapArray = new Student[maxSize];
        size = 0;
    }

    public void insert(Student s){
        if(size == heapArray.length) {
            throw new ArrayIndexOutOfBoundsException("Heap is full.");
        }

        heapArray[size] = s;
        int current = size;
        while(heapArray[current].compareTo(heapArray[parent(current)]) > 0){
            swap(current,parent(current));
            current = parent(current);
        }
        size++;
    }

    public Student remove(){
        if(size == 0){
            throw new NullPointerException("Heap is empty.");
        }

        Student root = heapArray[0];
        heapArray[0] = heapArray[size - 1];
        size--;
        heapify(0);

        return root;
    }

    private void heapify(int pos){
        if(isLeaf(pos)){
            return;
        }

        int leftChild = leftChild(pos);
        int rightChild = rightChild(pos);
        int max = pos;
        if(leftChild < size && heapArray[leftChild].compareTo(heapArray[max]) > 0){
            max = leftChild;
        }
        if(rightChild < size && heapArray[rightChild].compareTo(heapArray[max]) > 0){
            max = rightChild;
        }
        if(max != pos){
            swap(pos,max);
            heapify(max);
        }
    }

    private int parent(int pos) {
        return (pos - 1) / 2;
    }

    private int leftChild(int pos) {
        return 2 * pos + 1;
    }

    private int rightChild(int pos) {
        return 2 * pos + 2;
    }

    private boolean isLeaf(int pos) {
        return pos >= (size / 2) && pos < size;
    }

    private void swap(int a, int b) {
        Student temp = heapArray[a];
        heapArray[a] = heapArray[b];
        heapArray[b] = temp;
    }
}

class Student implements Comparable<Student>{
    private String name;
    private int age;
    private double grade;

    public Student(String name, int age, double grade) {
        this.name = name;
        this.age = age;
        this.grade = grade;
    }

    @Override
    public int compareTo(Student s) {
        return Double.compare(this.grade, s.grade);
    }

    @Override
    public String toString() {
        return name + "(age=" + age + ", grade=" + grade + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        StudentHeap studentHeap = new StudentHeap(10);
        studentHeap.insert(new Student("Alice", 20, 95.0));
        studentHeap.insert(new Student("Bob", 21, 88.5));
        studentHeap.insert(new Student("Charlie", 19, 90.3));
        studentHeap.insert(new Student("David", 22, 92.6));

        System.out.print("Heap: ");
        for(int i=0; i<4; i++) {
            System.out.print(studentHeap.remove() + " ");
        }
    }
}

输出结果如下：

Heap: Alice(age=20, grade=95.0) David(age=22, grade=92.6) Charlie(age=19, grade=90.3) Bob(age=21, grade=88.5) 

在示例中，我们创建了一个Student类，用于存储学生信息。然后创建了一个名为StudentHeap的最大堆对象，并向其中插入了四个Student对象。由于Student类实现了Comparable<Student>接口，所以我们可以直接通过次数变量grade来比较不同的学生。最后，我们从堆中移除最大值，并打印出剩余的值。