数据结构之二叉堆与优先队列

admin123

2019 年 11 月 04 日

2780 次浏览

暂无评论

加载中

1073字数

学习笔记

欢迎移步博主CSDN：[CSDN博客](https://blog.csdn.net/weixin_42327790/article/details/102903014)

# 数据结构之二叉堆与优先队列的学习
## 简介
二叉堆本质上是一种完全二叉树，采用顺序结构进行存储，它分为两种类型
* 最大堆
* 最小堆
最大堆的任何一个节点都大于或等于它的左右孩子节点
最小堆的任何一个节点都小于或等于它的孩子节点

---
## 二叉堆的用途与基本操作的实现
二叉堆是实现堆排序和优先队列的基础。
下面我们将用代码实现最小堆的上浮，下沉操作

**完整java代码**

二叉堆Heap类基本操作代码实现：
```java
package com.dataStructure.Heap;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * author zbl
 *
 * datetime 2019.11.4
 *
 */
//二叉堆
public class Heap {
    //采用数组存储二叉堆
    private int [] array;

@Override
    public String toString() {
        return "Heap{" +
                "array=" + Arrays.toString(array) +
                '}';
    }

//构造函数
    public Heap(int [] array , int length){
        this.array = Arrays.copyOf(array,length);
    }

//上浮调整
    public void upAdjust(){
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        //暂存最后一个节点数据
        int tmp = array[childIndex];
        //小顶堆
        while(childIndex > 0 && tmp<array[parentIndex]){
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = tmp;
    }

//下沉调整
    public void downAdjust(int parentIndex){
        int childIndex = parentIndex * 2 + 1;
        int tmp = array[parentIndex];
        while(childIndex < array.length - 1){
            //如果有右孩子，且右孩子小于左孩子，则定位到右孩子
            if(childIndex + 1 < array.length && array[childIndex + 1] < array[childIndex])
                childIndex++;
            //如果父节点最小，跳出
            if(tmp <= array[childIndex])
                break;
            //父节点下沉
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
        array[childIndex] = tmp;
    }
}

```

主函数：
```java

package com.dataStructure;

import com.dataStructure.Heap.Heap;

/**
 * author zbl
 *
 * datetime 2019.11.4
 *
 */
public class Main {

public static void main(String[] args) {
        int[] array = new int[]{8,7,6,5,4,3,2,1};
        Heap heap = new Heap(array,8);
        heap.upAdjust();
        System.out.println(heap.toString());

}
}

```

## 优先队列的实现

* 最大优先队列,无论入队顺序如何,都是当前优先级最大的元素优先出队
* 最小优先队列,无论入队顺序如何,都是当前优先级最小的元素优先出队

**下面是最小优先队列的实现代码**

二叉堆Heap类基本操作代码实现：
```java
package com.dataStructure.Heap;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * author zbl
 *
 * datetime 2019.11.5
 *
 */
//二叉堆
public class Heap {
    //采用数组存储二叉堆
    protected int [] array;
    //队列实际长度
    protected int size;
    public int[] getArray() {
        return array;
    }

public void setArray(int[] array) {
        this.array = array;
    }

@Override
    public String toString() {
        return "Heap{" +
                "array=" + Arrays.toString(this.array) +
                '}';
    }
    //空构造函数
    public Heap(){}
    //构造函数
    public Heap(int [] array){
        this.array = Arrays.copyOf(array,array.length);
    }

//上浮调整
    public void upAdjust(){
        int childIndex = this.size - 1;
        int parentIndex = (childIndex - 1) / 2;
        //暂存最后一个节点数据
        int tmp = this.array[childIndex];
        //小顶堆
        while(childIndex > 0 && tmp<this.array[parentIndex]){
            this.array[childIndex] = this.array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        this.array[childIndex] = tmp;
    }

//下沉调整
    public void downAdjust(int parentIndex){
        int childIndex = parentIndex * 2 + 1;
        int tmp = this.array[parentIndex];
        while(childIndex < this.size - 1){
            //如果有右孩子，且右孩子小于左孩子，则定位到右孩子
            if(childIndex + 1 < this.size && this.array[childIndex + 1] < this.array[childIndex])
                childIndex++;
            //如果父节点最小，跳出
            if(tmp <= this.array[childIndex])
                break;
            //父节点下沉
            this.array[parentIndex] = this.array[childIndex];
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
        this.array[childIndex] = tmp;
    }
}

```

最小优先队列PriorityQueue 类的实现：
```java
package com.dataStructure.Heap;

import java.util.Arrays;
/**
 * author zbl
 *
 * datetime 2019.11.5
 *
 */
public class PriorityQueue extends Heap {

public PriorityQueue(){
        this.array = new int[32];
    }
    //下沉调整 构建缺省值
    public void downAdjust(){
        super.downAdjust(0);
    }
    //出队
    public int deQueue() throws Exception{
        //队列为空
        if(this.size<0)
            throw new Exception("队列为空");
        //获取堆顶元素
        int x = this.array[0] ;
        this.array[0] = this.array[--this.size];
        downAdjust();
        return x;
    }

//入队
    public void enQueue(int key){
        //长度超出范围
        if(this.size >= this.array.length){
            resize();
        }
        this.array[this.size++] = key;
        upAdjust();
    }
    //扩容
    public void resize(){
        //容量翻倍
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(this.array,newSize);
    }

}

```
主函数:
```java
package com.dataStructure;

import com.dataStructure.Heap.Heap;
import com.dataStructure.Heap.PriorityQueue;

/**
 * author zbl
 *
 * datetime 2019.11.5
 *
 */
public class Main {

public static void main(String[] args) throws Exception{
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        System.out.println(priorityQueue.toString());
        priorityQueue.enQueue(5);
        System.out.println(priorityQueue.toString());
        priorityQueue.enQueue(10);
        System.out.println(priorityQueue.toString());
        priorityQueue.enQueue(2);
        System.out.println(priorityQueue.toString());
        priorityQueue.enQueue(7);
        System.out.println(priorityQueue.toString());
        System.out.println(priorityQueue.deQueue());
        System.out.println(priorityQueue.deQueue());
    }
}

```
## 参考文献

* 魏梦舒(@程序员小灰)著. 漫画算法--小灰的算法之旅 [M]. 电子工业出版社.

数据结构之二叉堆与优先队列