堆和优先队列

旧城等待， 2021-09-23 22:30 383阅读 0赞

# 什么是优先队列 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

# 为什么会使用优先队列 #

## 动态： ##

**任务处理中心随时都在处理各种各样的请求，也就是说不是一开始就确定了各种请求的优先级的，请求的优先级是不断地变化的。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]

# 堆的基本结构 #

**堆其实也是一棵树。**   
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]

**二叉堆的性质 ：**

**首先是一个完全二叉树**

**堆中某个节点的值总是不大于其父节点的值 ---->最大堆**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]

## 数组实现最大堆 ##

package MaxHeap;
    
    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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/7f63288824564cd991c56f9efbae2f8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/59eaa85c4907478da767bac4e0b907a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]: /images/20210923/7d37c694ccd04c558a11f052bb64800c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]: /images/20210923/b9bd702f233942a09d0a5670ddcff762.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]: /images/20210923/398e694a13c6436e8eb2ed231d9b21d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]: /images/20210923/0a2fe05aaee6423682d0dd06509c88e8.png