use core::fmt;
use std::{cmp, fmt::Debug};
mod heap_sort;
pub mod index;
pub use heap_sort::HeapSort;
pub use index::*;
fn parent(i: usize) -> usize {
(i - 1) / 2
}
fn left_child(i: usize) -> usize {
2 * i + 1
}
fn right_child(i: usize) -> usize {
2 * i + 2
}
#[derive(Clone, Default)]
pub struct PriorityQueue<K, F>
where
K: Ord,
F: Fn(&K, &K) -> cmp::Ordering,
{
heap: Vec<K>,
comparator: F,
}
impl<K: Ord> PriorityQueue<K, fn(&K, &K) -> cmp::Ordering> {
#[must_use]
pub fn new() -> Self {
Self {
heap: Vec::new(),
comparator: |v1, v2| v1.cmp(v2),
}
}
}
impl<K, F> PriorityQueue<K, F>
where
K: Ord,
F: Fn(&K, &K) -> cmp::Ordering,
{
#[must_use]
pub fn with_comparator(comparator: F) -> Self {
Self {
heap: Vec::new(),
comparator,
}
}
#[must_use]
pub fn len(&self) -> usize {
self.heap.len()
}
#[must_use]
#[inline(always)]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn insert(&mut self, key: K) {
self.heap.push(key);
self.swim(self.heap.len() - 1);
}
#[must_use]
pub fn peek(&self) -> Option<&K> {
self.heap.first()
}
#[must_use]
pub fn pop(&mut self) -> Option<K> {
if self.is_empty() {
return None;
}
let n = self.heap.len() - 1;
self.heap.swap(0, n);
let key = self.heap.pop()?;
self.sink(0);
debug_assert!(self.is_heap_ordered(0));
Some(key)
}
fn swim(&mut self, mut pos: usize) {
while pos > 0 && self.less(parent(pos), pos) {
self.heap.swap(parent(pos), pos);
pos = parent(pos);
}
}
fn sink(&mut self, mut pos: usize) {
while left_child(pos) < self.heap.len() {
let mut j = left_child(pos);
if j < self.heap.len() - 1 && self.less(j, j + 1) {
j += 1; }
if !self.less(pos, j) {
break;
}
self.heap.swap(pos, j);
pos = j;
}
}
fn less(&self, i: usize, j: usize) -> bool {
(self.comparator)(&self.heap[i], &self.heap[j]).is_lt()
}
fn is_heap_ordered(&self, pos: usize) -> bool {
if pos > self.heap.len() {
return true;
}
let left = left_child(pos);
let right = right_child(pos);
if left < self.heap.len() && self.less(pos, left)
|| right < self.heap.len() && self.less(pos, right)
{
return false;
}
self.is_heap_ordered(left) && self.is_heap_ordered(right)
}
}
#[must_use = "iterators are lazy and do nothing on their own"]
pub struct IntoIter<K, F>
where
K: Ord,
F: Fn(&K, &K) -> cmp::Ordering,
{
item: PriorityQueue<K, F>,
}
impl<K, F> Extend<K> for PriorityQueue<K, F>
where
K: Ord,
F: Fn(&K, &K) -> cmp::Ordering,
{
fn extend<I: IntoIterator<Item = K>>(&mut self, iter: I) {
for item in iter {
self.insert(item);
}
}
}
impl<K: Ord> FromIterator<K> for PriorityQueue<K, fn(&K, &K) -> cmp::Ordering> {
fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self {
let mut list = Self::new();
list.extend(iter);
list
}
}
impl<K: Debug, F> Debug for PriorityQueue<K, F>
where
K: Ord,
F: Fn(&K, &K) -> cmp::Ordering,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(&self.heap).finish()
}
}
impl<K, F> Iterator for IntoIter<K, F>
where
K: Ord,
F: Fn(&K, &K) -> cmp::Ordering,
{
type Item = K;
fn next(&mut self) -> Option<Self::Item> {
self.item.pop()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.item.len(), Some(self.item.len()))
}
}
impl<K, F> ExactSizeIterator for IntoIter<K, F>
where
K: Ord,
F: Fn(&K, &K) -> cmp::Ordering,
{
fn len(&self) -> usize {
self.item.len()
}
}
impl<K, F> IntoIterator for PriorityQueue<K, F>
where
K: Ord,
F: Fn(&K, &K) -> cmp::Ordering,
{
type Item = K;
type IntoIter = IntoIter<K, F>;
fn into_iter(self) -> Self::IntoIter {
IntoIter { item: self }
}
}
#[cfg(test)]
mod tests {
use rand::prelude::*;
use super::*;
#[test]
fn test_simple() {
let mut pq = PriorityQueue::new();
assert_eq!(pq.len(), 0);
assert!(pq.is_empty());
assert_eq!(pq.pop(), None);
pq.insert(1);
assert_eq!(pq.len(), 1);
assert!(!pq.is_empty());
assert_eq!(pq.peek(), Some(&1));
pq.insert(100);
assert_eq!(pq.len(), 2);
assert!(!pq.is_empty());
assert_eq!(pq.peek(), Some(&100));
assert_eq!(pq.pop(), Some(100));
assert_eq!(pq.len(), 1);
assert_eq!(pq.pop(), Some(1));
assert_eq!(pq.len(), 0);
assert!(pq.is_empty());
assert_eq!(pq.pop(), None);
assert_eq!(pq.pop(), None);
assert_eq!(pq.pop(), None);
}
fn get_biggest<T: Ord>(arr: &[T]) -> (usize, &T) {
arr.iter().enumerate().max_by(|a, b| a.1.cmp(b.1)).unwrap()
}
#[test]
fn test_big() {
let mut rand = rand::rng();
let mut vec = Vec::with_capacity(1000);
let mut pq = PriorityQueue::new();
assert_eq!(pq.pop(), None);
for item in vec.iter_mut() {
*item = rand.random_range(-100..=100);
pq.insert(*item);
}
while !pq.is_empty() {
let (i, &biggest) = get_biggest(&vec);
assert_eq!(pq.pop(), Some(biggest));
vec.swap_remove(i);
}
assert!(pq.is_empty());
assert_eq!(pq.len(), 0);
assert_eq!(pq.pop(), None);
assert_eq!(pq.pop(), None);
assert_eq!(pq.pop(), None);
}
}