如何使用 Java 实现最大堆? |21xrx.com

如何使用 Java 实现最大堆?

2023-06-16 13:38:05 深夜i -- --

在计算机科学中，堆是一种可以高效地插入或删除元素和查找最大元素或最小元素的数据结构。最大堆是其中一种，它保证父节点总是比它的子节点要大。在 Java 中，我们可以使用数组的形式来表示最大堆，并根据其特性进行实现。

以下是使用 Java 实现最大堆的代码示例：


public class MaxHeap {
  private int[] heap;
  private int size;
  public MaxHeap(int capacity) {
    heap = new int[capacity];
    size = 0;
  }
  
  public void insert(int value) {
    if (size == heap.length) {
      throw new IllegalStateException();
    }
    heap[size] = value;
    size++;
    siftUp();
  }
  public int remove() {
    if (size == 0) {
      throw new IllegalStateException();
    }
    int result = heap[0];
    heap[0] = heap[size - 1];
    size--;
    siftDown();
    return result;
  }
  private void siftUp() {
    int index = size - 1;
    while (index > 0 && heap[index] > heap[parent(index)]) {
      swap(index, parent(index));
      index = parent(index);
    }
  }
  private void siftDown() {
    int index = 0;
    while (index <= size && !isValidParent(index)) {
      int largerChildIndex = largerChildIndex(index);
      swap(index, largerChildIndex);
      index = largerChildIndex;
    }
  }
  private boolean isValidParent(int index) {
    if (!hasLeftChild(index))
      return true;
    
    boolean isValid = heap[index] >= leftChild(index);
    if (hasRightChild(index)) {
      isValid &= heap[index] >= rightChild(index);
    }
    return isValid;
  }
  private int largerChildIndex(int index) {
    if (!hasLeftChild(index))
      return index;
    
    if (!hasRightChild(index)) {
      return leftChild(index);
    }
    return leftChild(index) > rightChild(index) ? leftChild(index) : rightChild(index);
  }
  private boolean hasLeftChild(int index) {
    return leftChildIndex(index) <= size;
  }
  private boolean hasRightChild(int index) {
    return rightChildIndex(index) <= size;
  }
  private boolean hasParent(int index) {
    return parent(index) >= 0;
  }
  private int leftChild(int index) {
    return heap[leftChildIndex(index)];
  }
  private int rightChild(int index) {
    return heap[rightChildIndex(index)];
  }
  private int parent(int index) {
    return heap[(index - 1) / 2];
  }
  private int leftChildIndex(int index) {
    return index * 2 + 1;
  }
  private int rightChildIndex(int index) {
    return index * 2 + 2;
  }
  private void swap(int index1, int index2) {
    int temp = heap[index1];
    heap[index1] = heap[index2];
    heap[index2] = temp;
  }
}

在上述代码中，我们定义了一个最大堆类 `MaxHeap`，它包含了以下方法：

- `insert(value)`：插入一个值到堆中。

- `remove()`：移除并返回堆中的最大值。

- `siftUp()`：将插入的值向上移动，使其满足最大堆的特性。

- `siftDown()`：将移除最大值后的堆向下移动，使其满足最大堆的特性。

- `isValidParent(index)`：判断当前节点是否为父节点。

- `largerChildIndex(index)`：判断当前节点的较大子节点的索引。

- `hasLeftChild(index)`：判断当前节点是否有左子节点。

- `hasRightChild(index)`：判断当前节点是否有右子节点。

- `hasParent(index)`：判断当前节点是否有父节点。

- `leftChild(index)`：返回当前节点的左子节点的值。

- `rightChild(index)`：返回当前节点的右子节点的值。

- `parent(index)`：返回当前节点的父节点的值。

- `leftChildIndex(index)`：返回当前节点的左子节点索引。

- `rightChildIndex(index)`：返回当前节点的右子节点索引。

- `swap(index1, index2)`：交换两个节点。

使用上述代码，我们就可以轻松地实现最大堆。为了检验其正确性，可以新建一个测试类，以如下方式测试：


public class Main {
  public static void main(String[] args) {
    MaxHeap heap = new MaxHeap(10);
    
    heap.insert(10);
    heap.insert(5);
    heap.insert(15);
    heap.insert(20);
    
    int result = heap.remove();
    System.out.println(result); // Output: 20
  }
}

通过上述测试，我们可以看到最大堆已经正确地移除了最大的值 `20`，也证明了其正确性。

综上所述，我们已经成功使用 Java 实现了最大堆，并进行了一些简单的测试。相关的关键词包括：Java、最大堆、数据结构。

上一篇: idea打包java可执行jar包

下一篇: Java程序编译成什么文件

评论区

()

相似文章