堆的实现（java）

• 堆的基础表示
• • 数据的存储规则
  • 用数组存储堆中的数据
  • MaxHeap基本方法的实现
• 向堆中添加元素
• • 添加思路
• 取出堆中的最大元素
• 将数组转换为堆
• • MaxHeap构造函数
• 堆排序
• • 堆排序
  • 优化的堆排序

堆结构类似与二叉树（此处用最大堆举例），不同的是堆只用满足左右孩子均小于该节点值即可，由此，堆是一个完全二叉树（一层一层按顺序摆放数据）

由于堆中的数据存储方法满足完全二叉树（相当于顺序存储），故可以用数组顺序存储数据（从1开始）

由于后续删除、添加元素需要寻找节点的父亲节点、左孩子、右孩子，根据图示，易得出规律

public class MaxHeap >{
	private Array data;
	
	public MaxHeap(int capacity) {
		data=new Array<>(capacity);
	}
	public MaxHeap() {
		data=new Array<>();
	}
	
	//返回堆中元素的个数
	public int size() {
		return data.getSize();
	}
	
	//返回一个布尔值，表示堆是否为空
	public boolean isEmpty() {
		return data.isEmpty();
	}
	
	//返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
	private int parent(int index) {
		if(index==0)
			throw new IllegalArgumentException("Index 0 doesn't have parent.");
		return (index-1)/2;
	}
	
	//返回完全二叉树的数组表示中，一个索引所表示元素的左孩子节点
	private int leftChild(int index) {
		return index*2+1;
	}
	
	//返回完全二叉树的数组表示中，一个索引所表示元素的右孩子节点
		private int rightChild(int index) {
			return index*2+2;
		}
	}

首先在动态数组尾部添加元素

再向上寻找其父亲节点，比较父亲结点位置值，若该位置值大于父亲节点的值，间二者间的值进行交换，直至父亲结点值大于新添加的元素

代码实现

   //向堆中添加元素
		public void add(E e) {
			data.addLast(e);
			siftUp(data.getSize()-1);
		}
       private void siftUp(int k) {
    	   while(k>0&&data.get(parent(k)).compareTo(data.get(k))<0) {//只有在k位置存在且值大于父亲节点的情况下才swap
    		   data.swap(k, parent(k));
    		   k=parent(k);
    	   }
       }

取出最大元素很容易，问题就是如何对堆中其它元素进行操作

取出元素后，首先将数组末尾元素移到数组首部，填补空缺

再比较该结点与其孩子节点的值，选择大于该结点，且值较大的孩子结点进行交换

一直进行交换直至没有左右孩子或均大于左右孩子为止

代码实现

//取出堆中的最大元素
       public E extractMax() {
    	   E ret=findMax();
    	   data.swap(0, data.getSize()-1);
    	   data.removeLast();
    	   siftDown(0);
    	   return ret;
       }
       
       private void siftDown(int k) {
    	   while(leftChild(k)=0)
    				   break;
    		   data.swap(k, j);
    		   k=j;
    	   }
       }

想要将传入的数组原地转换为堆，方法很简单，只需找到倒数第一个非叶子节点，也就是最后一个节点的父亲节点（此处标为红色的位置），从此处依次往前，进行siftDown操作即可

MaxHeap中的heapify方法：

public MaxHeap(E[] arr) {
		data=new Array<>(arr);
		for(int i=parent(arr.length-1);i>=0;i--)
			siftDown(i);
	}

由于堆自身的特性，我们可以知道，索引为0的位置，永远存放堆中的最大元素。据此，我们可以利用堆对数组进行排序

	public static > void sort(E[] data) {
		MaxHeap maxHeap=new MaxHeap<>();
		for(E e:data)
		   maxHeap.add(e);
		for(int i=data.length-1;i>=0;i--) {
			data[i]=maxHeap.extractMax();
		}
	}

想要对堆排序进行优化，我们可以对数组进行原地heapify，再对最大值进行处理



如图示，就是要原地实现数组的heapify,再将堆中第一个元素与最后一个元素交换位置。

• 交换位置后，堆可能不会满足最大堆的性质（图二中标黄的部分），所以要对第一个元素进行heapify，使其满足堆的性质。
• 接下来再重复这个操作

public static > void sort2(E[] data) {
		if(data.length<=1) return ;
		//将普通数组转换为堆的形式
		for(int i=(data.length-2)/2;i>=0;i--) {
	        siftDown(data,i,data.length);
	    //再对堆进行swap,siftDown操作
	    for(i=data.length-1;i>=0;i--) {
	    	swap(data,0,i);
	    	siftDown(data,0,i);
	    }
	}
		}
	//对data[0,n)所形成的最大堆中，索引为k的元素，执行siftDown
	private static > void siftDown(E[] data,int k,int n) {
	    while(2*k+1=0)
	    	    break;
	    	swap(data,k, j);
	    	k=j;
	    	   }
	       }
    private static  void swap(E[] arr,int i,int j){
		E tmp=arr[i];
		arr[i]=arr[j];
		arr[j]=tmp;
	}