Dsa Using Java 简明教程

DSA using Java - Heap

Overview

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

Heap represents a special tree based data structure used to represent priority queue or for heap sort. We’ll going to discuss binary heap tree specifically.

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

Binary heap tree can be classified as a binary tree with two constraints −

Completeness − Binary heap tree is a complete binary tree except the last level which may not have all elements but elements from left to right should be filled in.
Heapness − All parent nodes should be greater or smaller to their children. If parent node is to be greater than its child then it is called Max heap otherwise it is called Min heap. Max heap is used for heap sort and Min heap is used for priority queue. We’re considering Min Heap and will use array implementation for the same.

Basic Operations

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

Following are basic primary operations of a Min heap which are following.

Insert − insert an element in a heap.
Get Minimum − get minimum element from the heap.
Remove Minimum − remove the minimum element from the heap

Insert Operation

Whenever an element is to be inserted. Insert element at the end of the array. Increase the size of heap by 1.

堆化元素，同时堆属性被破坏。比较元素与父值，并在需要时交换它们。

. Heap up the element while heap property is broken. Compare element with parent’s value and swap them if required.

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);
      }
   }
}

Get Minimum

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

Get the first element of the array implementing the heap being root.

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

Remove Minimum

Whenever an element is to be removed. Get the last element of the array and reduce size of heap by 1.

堆化元素，同时堆属性被破坏。比较元素与子值，并在需要时交换它们。

. Heap down the element while heap property is broken. Compare element with children’s value and swap them if required.

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);
   }
}

Heap Implementation

Heap.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);
      }
   }
}

Demo Program

HeapDemo.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());
   }
}

如果我们编译并运行上述程序，它将生成以下结果 -

If we compile and run the above program then it would produce following result −

1
2