Image Source: Wikipedia

A heap is either a min-heap or a max-heap. A max-heap for example consistently stores the largest item at the top, ready for priority popping.

Algorithm:

• To push an item, place it in a new node at the bottom. Then recursively swap it upward until the heap property is restored.
• To pop the root node, move the last item over the old root. Then recursively swap it downward until the heap property is restored.

Average time complexity: $O(log(n))$

Rust implementation:

struct MaxHeap<T> {
    items: Vec<T>,
}

impl<T: Ord + Copy> MaxHeap<T> {
    pub fn new() -> MaxHeap<T> {
        MaxHeap { items: Vec::new() }
    }

    /// Restores the max-heap property when an item is pushed.
    fn heapify_new(&mut self, index: usize) {
        if index == 0 {
            return;
        }
        let parent_index = (index - 1) / 2;
        if index < self.items.len() && self.items[index] > self.items[parent_index] {
            self.items.swap(index, parent_index);
            self.heapify_new(parent_index);
        }
    }

    pub fn push(&mut self, item: T) {
        self.items.push(item);
        self.heapify_new(self.items.len() - 1);
    }

    /// Restores the max-heap property when an item is popped.
    fn heapify_deleted(&mut self, index: usize) {
        let mut max_index = index;
        let left_index = index * 2 + 1;
        let right_index = index * 2 + 2;
        if left_index < self.items.len() && self.items[left_index] > self.items[index] {
            max_index = left_index;
        } else if right_index < self.items.len() && self.items[right_index] > self.items[right_index] {
            max_index = right_index;
        }
        if max_index != index {
            self.items.swap(index, max_index);
            self.heapify_deleted(max_index);
        }
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.items.is_empty() {
            None
        } else {
            let result = Some(self.items[0]);
            self.items[0] = self.items[self.items.len() - 1];
            self.items.remove(self.items.len() - 1);
            self.heapify_deleted(0);
            result
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn main() {
        let mut heap = MaxHeap::new();
        heap.push(2);
        heap.push(1);
        heap.push(7);
        heap.push(10);
        heap.push(3);
        assert_eq!(heap.pop(), Some(10));
        assert_eq!(heap.pop(), Some(7));
        assert_eq!(heap.pop(), Some(3));
        assert_eq!(heap.pop(), Some(2));
        assert_eq!(heap.pop(), Some(1));
        assert_eq!(heap.pop(), None);
    }
}