手把手写一个集合框架（四）堆与优先队列

      之前几篇文章我们实现了数组、链表、栈和队列。这篇文章，我们来介绍堆的实现以及基于堆的优先队列的实现。

• 最大堆的实现

• 最大堆的构造方法，元素需要实现可比较

public class MaxHeap<E extends Comparable<E>> {	
private Array<E> data;    
//空构造函数
public MaxHeap(){
   data = new Array<>();
} 

//初始容量的构造函数   
public MaxHeap(int Capacity){/
	data = new Array<>(Capacity);
   }
}

• 最大堆的基本方法

//判断堆是否为空
public boolean isEmpty(){    
   return data.getSize()==0;
}

//判断堆的元素个数
public int getSize(){    
    return data.getSize();
}

• 计算节点下标

public int parent(int index){//计算父节点下标
     if(index<=0)	
      throw new IllegalArgumentException("index error");    
    return (index-1)<<1;
}

//返回右孩子节点
public int leftChild(int index){     
    return index>>1+1;
}

//返回左孩子节点
public int rightChild(int index){     
    return index>>1+2;
}

• 向堆中添加元素

//新增一个元素
public void add(E e){
   data.addLast(e);
   SiftUp(data.getSize()-1);//元素上浮
}

/******核心*****/
//元素上浮
private void SiftUp(int i) {    
   while(i>0&&data.get(parent(i)).compareTo(data.get(i))<0){	     
     int j = parent(i);
     data.swap(i, j);
     i = j;
  }		
}

• 查看堆顶元素

//查看最大值
public E findMax(){     
     if(data.getSize() == 0)          
       throw new IllegalArgumentException("error.");    
  return data.get(0);
}

• 获取最大值，取走堆顶元素

public E  extractMax(){//取最大值    
    E ret = findMax();
    data.swap(0, data.getSize()-1);
    data.removeLast();
    siftDown(0);//元素下沉    
    return ret;
}        
/****核心*******/
private void siftDown(int i) {	
   while(leftChild(i)<data.getSize()){	      
     int j = leftChild(i);  //这里比较左右孩子节点谁大，如果右节点大     
   if(j+1<data.getSize()&& data.get(j+1).compareTo(data.get(j))>0)
	 j++; //这里说明当前节点大于叶子节点，满足堆性质，则break     
   if(data.get(i).compareTo(data.get(j))>=0) 
        break;
    data.swap(i, j);//否则交换根节点和叶子节点
    i = j;//下一次查找
   }		
}

• 最后新增一个构造函数，用于将一个数组进行堆化

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

• 最大堆/最小堆的应用
  LeetCode347-频次最高的K个元素

• 优先队列的实现

• 首先，优先队列也是队列的一种,因此先给出上一篇队列接口的定义

public interface Queue<E> {    
    int getSize();    
    boolean isEmpty();    
    void enqueue(E e);    
    E dequeue();    
    E getFront();
}

• 优先队列的构造函数

public class PriorityQueue<E extends Comparable<E>> implements Queue<E>
{
     private MaxHeap<E> maxHeap;    
     public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }
}

• 优先队列的基本功能

//队列元素个数
public int getSize(){   
    return maxHeap.size();
}

//队列是否为空
public boolean isEmpty(){ 
   return maxHeap.isEmpty();
}

//获取队列顶元素
public E getFront(){   
     return maxHeap.findMax();
}

//入队一个元素
public void enqueue(E e){
    maxHeap.add(e);
}

//移除队列顶部元素
public E dequeue(){   
    return maxHeap.extractMax();
}

• 优先队列应用
  

1. 带有优先级的任务
   

2. LeetCode347-频次最高的K个元素

• 总结

       堆其实也可以看成一种树状结构。我们从上到下，使用数组的方式按照顺序的下标来表示一个堆。当加入元素，就相当于在数组最后添加，然后将元素进行上浮操作。当提取出堆顶元素，相当于去除数组index=0的元素，此时将最后元素填充第一个元素，然后执行下沉操作。查看堆顶元素，也就是查看index=0的元素。

       下一篇，我们一起来实现二分搜索树的相关操作。后面更精彩哦！