本文将为我们提供堆排序工作的完整概述，稍后我们将学习在Java中实现二进制堆。

什么是堆排序？

堆基本上是一个基于树的数据结构。
它具有节点。
节点由某些元素组成。
每个节点包含一个元素。

节点可能有孩子。
如果没有孩子，则称为叶子。

有两个规则要遵循：

• 每个节点的值必须小于或者等于其子节点中存储的所有值。

• 它具有最小的高度。

堆在提取最小或者最大元素方面非常有效。

最小堆

最小堆是完整的二叉树，其中根元素的值小于或者等于子元素中的任何一个。

最小堆的表示

Arr [(i-1)/2]：这将返回父节点。

Arr [(2 * i)+1]：这将返回左子节点。

Arr [(2 * i)+ 2]：这将返回右子节点。

有最小堆的某些方法：

• insert()：在树的末尾添加一个新键。如果新键的大小大于父键的大小，则无需执行任何操作，否则，我们必须遍历设置堆属性。

• getMin()：此方法有助于返回根元素。

• extractMin()：此方法返回最小元素。

现在转到最大堆。

最大堆

最大堆是完整的二叉树，其中根元素的值大于或者等于子元素中的任何一个。

最大堆也包含几种方法！

• Insert()：它将在堆中插入一个元素。

• Delete()：它将从堆中删除一个元素。

• FindMax()：它将从堆中找到最大的元素。

• printHeap()：它将打印堆的内容

现在，让我通过图和稍后的Java代码向我们展示堆的实现。

Java中的堆实现

图表：

上图显示了Java中的二进制堆。
如我们所知，有两个堆：最小堆和最大堆，这是一个图：

现在，进入下一部分，我们将看到如何在Java中实现二进制堆。

代码：

public class BinaryHeap {
	
	private static final int d= 2;
	private int[] heap;
	private int heapSize;
	
	/**
	 * This will initialize our heap with default size. 
	 */
	public BinaryHeap(int capacity){
		heapSize = 0;
		heap = new int[ capacity+1];
		Arrays.fill(heap, -1);
		
	}
	
	/**
	 *  This will check if the heap is empty or not
	 *  Complexity: O(1)
	 */
	public boolean isEmpty(){
		return heapSize==0;
	}
	
	/**
	 *  This will check if the heap is full or not
	 *  Complexity: O(1)
	 */
	public boolean isFull(){
		return heapSize == heap.length;
	}
	
	
	private int parent(int i){
		return (i-1)/d;
	}
	
	private int kthChild(int i,int k){
		return d*i  +k;
	}
	
	/**
	 *  This will insert new element in to heap
	 *  Complexity: O(log N)
	 *  As worst case scenario, we need to traverse till the root
	 */
	public void insert(int x){
		if(isFull())
			throw new NoSuchElementException("Heap is full, No space to insert new element");
		heap[heapSize++] = x;
		heapifyUp(heapSize-1);
	}
	
	/**
	 *  This will delete element at index x
	 *  Complexity: O(log N)
	 * 
	 */
	public int delete(int x){
		if(isEmpty())
			throw new NoSuchElementException("Heap is empty, No element to delete");
		int key = heap[x];
		heap[x] = heap[heapSize -1];
		heapSize--;
		heapifyDown(x);
		return key;
	}
	/**
	 *  This method used to maintain the heap property while inserting an element.
	 *  
	 */
	private void heapifyUp(int i) {
		int temp = heap[i];
		while(i>0 && temp > heap[parent(i)]){
			heap[i] = heap[parent(i)];
			i = parent(i);
		}
		heap[i] = temp;
	}
	
	/**
	 *  This method used to maintain the heap property while deleting an element.
	 *  
	 */
	private void heapifyDown(int i){
		int child;
		int temp = heap[i];
		while(kthChild(i, 1) < heapSize){
			child = maxChild(i);
			if(temp < heap[child]){ heap[i] = heap[child]; }else break; i = child; } heap[i] = temp; } private int maxChild(int i) { int leftChild = kthChild(i, 1); int rightChild = kthChild(i, 2); return heap[leftChild]>heap[rightChild]?leftChild:rightChild;
	}
	
	/**
	 *  This method used to print all element of the heap
	 *  
	 */
	public void printHeap()
	    {
	        System.out.print("nHeap = ");
	        for (int i = 0; i < heapSize; i++)
	            System.out.print(heap[i] +" ");
	        System.out.println();
	    }
	/**
	 *  This method returns the max element of the heap.
	 *  complexity: O(1)
	 */
	 public int findMax(){
		 if(isEmpty())
			 throw new NoSuchElementException("Heap is empty.");
		 return heap[0];
	 }
	 
	 public static void main(String[] args){
		 BinaryHeap maxHeap = new BinaryHeap(10);
		 maxHeap.insert(10);
		 maxHeap.insert(4);
		 maxHeap.insert(9);
		 maxHeap.insert(1);
		 maxHeap.insert(7);
		 maxHeap.insert(5);
		 maxHeap.insert(3);
		 
		 maxHeap.printHeap();
		 maxHeap.delete(5);
		 maxHeap.printHeap();
		 
	 }
}