使用 Java 的 DSA - 堆

---

概述

堆表示一种特殊的基于树的数据结构，用于表示优先级队列或用于堆排序。我们将具体讨论二叉堆树。

二叉堆树可以分类为具有两个约束的二叉树 -

• 完整性- 二叉堆树是一个完整的二叉树，除了最后一层可能没有所有元素，但应填充从左到右的元素。

• 堆- 所有父节点都应大于或小于其子节点。如果父节点大于其子节点，则称为最大堆，否则称为最小堆。最大堆用于堆排序，最小堆用于优先级队列。我们正在考虑最小堆并将使用数组实现。

基本操作

以下是最小堆的基本主要操作。

• 插入- 在堆中插入一个元素。

• 获取最小值- 从堆中获取最小元素。

• 删除最小值- 从堆中删除最小元素

插入操作

• 每当要插入元素时。在数组末尾插入元素。将堆大小增加 1。

• 当堆属性被破坏时，将元素堆起来。将元素与父元素的值进行比较，并根据需要交换它们。

public void insert(int value) {            
   size++;
   intArray[size - 1] = value;
   heapUp(size - 1);
}

private void heapUp(int nodeIndex){
   int parentIndex, tmp;
   if (nodeIndex != 0) {
      parentIndex = getParentIndex(nodeIndex);
      if (intArray[parentIndex] > intArray[nodeIndex]) {
         tmp = intArray[parentIndex];
         intArray[parentIndex] = intArray[nodeIndex];
         intArray[nodeIndex] = tmp;
         heapUp(parentIndex);
      }
   }
}

获取最小值

获取实现堆的数组的第一个元素是根。

public int getMinimum(){
   return intArray[0];
}

删除最小值

• 每当要删除一个元素时。获取数组的最后一个元素并将堆大小减 1。

• 当堆属性被破坏时，将元素堆下来。将元素与子元素的值进行比较，并根据需要交换它们。

public void removeMin() {
   intArray[0] = intArray[size - 1];
   size--;
   if (size > 0)
      heapDown(0);
}

private void heapDown(int nodeIndex){
   int leftChildIndex, rightChildIndex, minIndex, tmp;
   leftChildIndex = getLeftChildIndex(nodeIndex);
   rightChildIndex = getRightChildIndex(nodeIndex);
   if (rightChildIndex >= size) {
      if (leftChildIndex >= size)
         return;
      else
         minIndex = leftChildIndex;
   } else {
      if (intArray[leftChildIndex] <= intArray[rightChildIndex])
         minIndex = leftChildIndex;
      else
         minIndex = rightChildIndex;
   }
   if (intArray[nodeIndex] > intArray[minIndex]) {
      tmp = intArray[minIndex];
      intArray[minIndex] = intArray[nodeIndex];
      intArray[nodeIndex] = tmp;
      heapDown(minIndex);
   }
}

堆实现

堆.java

package com.tutorialspoint.datastructure;

public class Heap {
   private int[] intArray;
   private int size;

   public Heap(int size){
      intArray = new int[size];
   }

   public boolean isEmpty(){
      return size == 0;
   }

   public int getMinimum(){
      return intArray[0];
   }

   public int getLeftChildIndex(int nodeIndex){
      return 2*nodeIndex +1;
   }

   public int getRightChildIndex(int nodeIndex){
      return 2*nodeIndex +2;
   }

   public int getParentIndex(int nodeIndex){
      return (nodeIndex -1)/2;
   }

   public boolean isFull(){
      return size == intArray.length;
   }

   public void insert(int value) {            
      size++;
      intArray[size - 1] = value;
      heapUp(size - 1);
   }

   public void removeMin() {
      intArray[0] = intArray[size - 1];
      size--;
      if (size > 0)
         heapDown(0);
   }

   /**
   * Heap up the new element,until heap property is broken. 
   * Steps:
   * 1. Compare node's value with parent's value. 
   * 2. Swap them, If they are in wrong order.
   * */
   private void heapUp(int nodeIndex){
      int parentIndex, tmp;
      if (nodeIndex != 0) {
         parentIndex = getParentIndex(nodeIndex);
         if (intArray[parentIndex] > intArray[nodeIndex]) {
            tmp = intArray[parentIndex];
            intArray[parentIndex] = intArray[nodeIndex];
            intArray[nodeIndex] = tmp;
            heapUp(parentIndex);
         }
      }
   }

   /**
   * Heap down the root element being least in value,until heap property is broken. 
   * Steps:
   * 1.If current node has no children, done.  
   * 2.If current node has one children and heap property is broken, 
   * 3.Swap the current node and child node and heap down.
   * 4.If current node has one children and heap property is broken, find smaller one  
   * 5.Swap the current node and child node and heap down.
   * */
   private void heapDown(int nodeIndex){
      int leftChildIndex, rightChildIndex, minIndex, tmp;
      leftChildIndex = getLeftChildIndex(nodeIndex);
      rightChildIndex = getRightChildIndex(nodeIndex);
      if (rightChildIndex >= size) {
         if (leftChildIndex >= size)
            return;
         else
            minIndex = leftChildIndex;
      } else {
         if (intArray[leftChildIndex] <= intArray[rightChildIndex])
            minIndex = leftChildIndex;
         else
            minIndex = rightChildIndex;
      }
      if (intArray[nodeIndex] > intArray[minIndex]) {
         tmp = intArray[minIndex];
         intArray[minIndex] = intArray[nodeIndex];
         intArray[nodeIndex] = tmp;
         heapDown(minIndex);
      }
   }
}

演示程序

堆演示.java

package com.tutorialspoint.datastructure;

public class HeapDemo {
   public static void main(String[] args){
      Heap heap = new Heap(10);
       /*                     5                //Level 0
        * 
        */
      heap.insert(5);
       /*                     1                //Level 0
        *                     |
        *                 5---|                //Level 1
        */
      heap.insert(1);
       /*                     1                //Level 0
        *                     |
        *                 5---|---3            //Level 1
        */
      heap.insert(3);
       /*                     1                //Level 0
        *                     |
        *                 5---|---3            //Level 1
        *                 |
        *              8--|                    //Level 2
        */
      heap.insert(8);
      /*                     1                //Level 0
       *                     |
       *                 5---|---3            //Level 1
       *                 |
       *              8--|--9                 //Level 2
       */
      heap.insert(9);
      /*                     1                 //Level 0
       *                     |
       *                 5---|---3             //Level 1
       *                 |       |
       *              8--|--9 6--|             //Level 2
       */
      heap.insert(6);
      /*                     1                 //Level 0
       *                     |
       *                 5---|---2             //Level 1
       *                 |       |
       *              8--|--9 6--|--3          //Level 2
       */
      heap.insert(2);

      System.out.println(heap.getMinimum());

      heap.removeMin();
      /*                     2                 //Level 0
       *                     |
       *                 5---|---3             //Level 1
       *                 |       |
       *              8--|--9 6--|             //Level 2
       */
      System.out.println(heap.getMinimum());   
   }
}

如果我们编译并运行上面的程序，那么它将产生以下结果 -

1
2