【玩转数据结构】----优先队列和堆

序言

优先队列和堆

---

一、什么是优先队列

二、堆的基础表示

1.堆的基本结构

2.数组来表示完全二叉树

• 优化上面的结构
  

三、实现最大堆

package com.zcw.data.maxheap;

import com.zcw.data.array.Array;

/**
 * @ClassName : MaxHeap
 * @Description : 实现最大堆
 * @Author : Zhaocunwei
 * @Date: 2020-08-07 14:16
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> 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;
    }
}

四、向堆中添加元素和Sift Up

• 从52的父节点的父节点进行比较，调整为二叉树，完成堆的性质
  

 public void swap(int i, int j){
        if(i<0 || i>=size || j<0 || j>=size){
            throw new IllegalArgumentException("Index is illegal.");
        }
        E t = data[i];
        data[i] =data[j];
        data[j] =t;
    }

//向堆中添加元素
    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){
            data.swap(k,parent(k));
            k = parent(k);
        }
        
    }

五、从堆中取出元素

上图是不符合堆的性质，需要进行下沉调整，跟两个孩子进行比较，与最大的交换位置：

 //看堆中的最大元素
    public E findMax(){
        if(data.getSize() ==0){
            throw  new IllegalArgumentException("Can not findMax when heap is empty.");
        }
        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 k){
        while(leftChild(k) < data.getSize()){
            int j = leftChild(k);
            if(j +1< data.getSize() && data.get(j+1).compareTo(data.get(j))>0){
                j= rightChild(k);
            }
            // data[j] 是 leftChild 和 rightChild 中的最大值
            if(data.get(k).compareTo(data.get(j)) >= 0){
                break;
            }
            data.swap(k,j);
            k = j;
        }
    }

六、Heapify 和 Replace

• replace
  

//取出堆中的最大元素，并且替换成元素E
    public E replace(E e){
        E ret =findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }

• heapify
  将任意数组整理成堆的形状
  
• 数组表示完全二叉树
  
  
  
  
  

 public Array(E[] arr){
        data =(E[])new Object[arr.length];
        for(int i=0;i<arr.length;i++){
            data[i]= arr[i];
        }
        size = arr.length;
    }

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

七、基于堆的优先队列

package com.zcw.data.maxheap;

import com.zcw.data.queue.Queue;

/**
 * @ClassName : PriorityQueue
 * @Description : 优先队列
 * @Author : Zhaocunwei
 * @Date: 2020-08-07 15:25
 */
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
    private MaxHeap<E> maxHeap;
    public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }
   @Override
    public int getSize(){
        return maxHeap.size();
   }
   @Override
    public boolean isEmpty(){
        return maxHeap.isEmpty();
   }
   @Override
    public E getFront(){
        return maxHeap.findMax();
   }
   @Override
    public void enqueue(E e){
        maxHeap.add(e);
   }
   @Override
    public E dequeue(){
        return maxHeap.extractMax();
   }
   
}