《恋上数据结构与算法》笔记（十七）：优先级队列 (二叉堆实现)

水深无声 2022-12-31 01:15 68阅读 0赞

### 一、优先级队列（Priority Queue） ###

> 队列相关的链接 : [队列][Link 1]

*  普通的队列是`先进先出`原则。
 *  优先级队列是按照`优先级高低`进行出队，比如将`优先级最高`的元素作为`队头`优先出队。
 *  使用场景：
    
     *  医院急诊根据病人病情和挂号时间决定谁先看病。
     *  操作系统的多任务调度，队列元素是任务，优先级是`任务类型`。

### 二、优先级队列（Priority Queue）底层实现 ###

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

*  通过`最大堆`来实现优先级队列。

public class PriorityQueue<E> { 
        private BinaryHeap<E> heap = new BinaryHeap<>();
    
        public PriorityQueue(Comparator<E> comparator) { 
            heap = new BinaryHeap<>(comparator);
        }
    
        public PriorityQueue() { 
            this(null);
        }
    
        public int size() { 
            return heap.size();
        }
    
        public boolean isEmpty() { 
            return heap.isEmpty();
        }
    
        public void clear() { 
            heap.clear();
        }
    
        public void enQueue(E element) { 
            heap.add(element);
        }
    
        public E deQueue() { 
            return heap.remove();
        }
    
        /** * 获取优先级最高的元素,即堆顶元素 * * @return */
        public E front() { 
            return heap.get();
        }
    }

public class Person implements Comparable<Person> { 
        private String name;
        private int boneBreak;
    
        public Person(String name, int boneBreak) { 
            this.name = name;
            this.boneBreak = boneBreak;
        }
    
        @Override
        public int compareTo(Person person) { 
            return this.boneBreak - person.boneBreak; // 表示boneBreak大的优先级就大
        }
    
        @Override
        public String toString() { 
            return "Person [name=" + name + ", boneBreak=" + boneBreak + "]";
        }
    }

public class Main { 
    
    	public static void main(String[] args) { 
    		PriorityQueue<Person> queue = new PriorityQueue<>();
    		queue.enQueue(new Person("Jack", 2));
    		queue.enQueue(new Person("Rose", 10));
    		queue.enQueue(new Person("Jake", 5));
    		queue.enQueue(new Person("James", 15));
    
    		while (!queue.isEmpty()) { 
    			System.out.println(queue.deQueue());
    		}
    	}
    }

Person [name=James, boneBreak=15]
    Person [name=Rose, boneBreak=10]
    Person [name=Jake, boneBreak=5]
    Person [name=Jack, boneBreak=2]

[Link 1]: https://blog.csdn.net/m0_37989980/article/details/105460922
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221120/101ee1d52f334d32ba4bd918a3125c33.png