在本教程中，我们将看到如何在Java中实现堆。

我将划分堆中的多个部分，使其更加理解。

什么是堆？

一个 heap是一个具有一些特殊属性的树，所以节点的值应大于或者等于(小于或者等于MIN堆的情况下)节点和树的子项应该是完整的二叉树。

二元堆

Binary heaps是那些最多可容纳2个孩子的堆。
我们将在接下来的几个部分中使用二进制堆。

了解完整的二叉树

完整的二叉树是一个二进制树，其叶子在h或者h-1级，其中h是树的高度。

左子索引= 2 *(其父索引的索引)+1右侧索引= 2 *(其父级的索引)+2

堆的类型

有两种类型的堆。

• 最大堆
• 闵堆

max heap：它是 binary heap其中节点的值大于节点的左左和右子。

闵堆：它是 binary heap其中节点的值小于节点的左左和右子。

heapizing一个元素：

创建堆后，它可能无法满足堆属性。
为了再次使其堆，我们需要调整堆的位置，并且此过程称为 heapifying要素。
为了创建一个最大堆，我们会将当前元素与其子组进行比较并找到最大值，如果当前元素不是最大值，则将其更高的左或者右侧的子元素交换。

Leapizing Element的Java代码I：

public static void heapify(int[] arr, int i, int size) {
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		int max;
		if (left <= size && arr[left] > arr[i]) {
			max = left;
		} else {
			max = i;
		}
 
		if (right <= size && arr[right] > arr[max]) {
			max = right;
		}
		//If max is not current node, exchange it with max of left and right child
		if (max != i) {
			exchange(arr, i, max);
			heapify(arr, max, size);
		}
	}

堆排序的步骤

• 将数组表示为完整的二叉树。
• 左孩子将在 2*i+1地点
• 合适的孩子将在 2*i+2位置。
• 建立一堆。
• 所有叶节点都已满足堆属性，因此我们不需要加热它们。
• 最后的叶节点将出现在 (n-1)th位置，所以它的父母将在 (n-1)/2位置，因此 (n-1)/2将是最后一个非叶节点的位置。
• 迭代非叶节点和 heapify要素。
• 建立堆后， max element将是堆的根源。我们会与之交换 (n-1)th位置，使得最大的元素将在适当的位置，并通过减少n的大小从堆中取出。
• 交换最大元素时，它可能会干扰最大堆属性，所以我们需要再次 heapify它。
• 完成上述步骤后，直到没有堆中的元素，我们将在最后进行排序阵列。

堆的Java代码排序

package org.igi.theitroad;
import java.util.*;
 
public class HeapSortMain {
 
   public static void buildheap(int []arr) {
      
    /*
     * As last non leaf node will be at (arr.length-1)/2 
     * so we will start from this location for heapifying the elements
     * */
    for(int i=(arr.length-1)/2; i>=0; i--){
           heapify(arr,i,arr.length-1);
      }
   }
 
   public static void heapify(int[] arr, int i,int size) { 
      int left = 2*i+1;
      int right = 2*i+2;
      int max;
      if(left <= size && arr[left] > arr[i]){
         max=left;
      } else {
         max=i;
      }
 
      if(right <= size && arr[right] > arr[max]) {
         max=right;
      }
      //If max is not current node, exchange it with max of left and right child
      if(max!=i) {
         exchange(arr,i, max);
         heapify(arr, max,size);
      }
   }
 
   public static void exchange(int[] arr,int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t; 
   }
 
   public static int[] heapSort(int[] arr) {
     
      buildheap(arr);
      int sizeOfHeap=arr.length-1;
      for(int i=sizeOfHeap; i>0; i--) {
         exchange(arr,0, i);
         sizeOfHeap=sizeOfHeap-1;
         heapify(arr, 0,sizeOfHeap);
      }
      return arr;
   }
 
   public static void main(String[] args) {
      int[] arr={1,10,16,19,3,5};
      System.out.println("Before Heap Sort : ");
      System.out.println(Arrays.toString(arr));
      arr=heapSort(arr);
      System.out.println("=====================");
      System.out.println("After Heap Sort : ");
      System.out.println(Arrays.toString(arr));
   }
}

时间和空间复杂性

时间复杂性：最佳案例：

O(nlogn)平均案例： O(nlogn)最坏的情况下 ： O(nlogn)空间复杂性：由于堆排序是归档排序算法，空间复杂性是 o(1)。
除了在堆中交换变量之外，我们不需要任何另外的空间。