Module std::collections::heap

Binary heap collection and utilities.

This module provides an allocating binary heap collection type, BinaryHeap as well as methods for in-place binary heaps over raw slices (heapify_by, sift_up_by, sift_down_by, ...).

Structs

Functions

• fn heapify_by<T, F>(self: &mut [T], f: F)

  F: CompareFunction<T>

  source

  Reorder the elements of a slice so they satisfy the (max) heap property.

  Example

  use std::collections::heap::heapify_by;
  use std::cmp::compare;
  
  let v = [3, 5, 1, 2, 9, 8];
  v[..].heapify_by(compare::<i32>);
  
  assert_eq!(v[0], 9); // max element
  Run this example

• fn heapify_tail_by<T, F>(self: &mut [T], start: usize, f: F)

  F: CompareFunction<T>

  source

  Reorder the elements of a slice so they satisfy the (max) heap property.

  This variant assumes that the slice before start already satisfies the heap property and sifts up the elements in the tail.

  The method is adaptive and will perform a standard heapification if that would be more efficient (if the tail is too long with respect to the existing heap in the head).

  Example

  use std::collections::heap::{heapify_by, heapify_tail_by};
  use std::cmp::compare;
  
  let v = [3, 5, 1, 2, 9, 8];
  v[0..4].heapify_by(compare::<i32>);
  v[..].heapify_tail_by(4, compare::<i32>);
  
  assert_eq!(v[0], 9); // max element
  Run this example

• fn sort_heap_by<T, F>(self: &mut [T], f: F)

  F: CompareFunction<T>

  source

  Sorts an array satisfying the max heap property in ascending order.

  Example

  use std::collections::heap::{heapify_by, sort_heap_by};
  use std::cmp::compare;
  
  fn heapsort(slice: &mut [i32]) {
      slice.heapify_by(compare::<i32>);
      slice.sort_heap_by(compare::<i32>);
  }
  
  let arr = [3, 5, 1, 2, 9, 8];
  arr[..].heapsort();
  
  assert_eq!(arr[..], &[1, 2, 3, 5, 8, 9]);
  Run this example

• fn sift_up_by<T, F>(self: &mut [T], pos: usize, f: F)

  F: CompareFunction<T>

  source

  Sifts an element up the heap until it reaches its correct position.

  This is used e.g. to restore the heap property after appending an element to the end of the heap.

  Example

  use std::collections::heap::{heapify_by, sift_up_by};
  use std::cmp::compare;
  
  let v = [1, 2, 3, 4, 5];
  v[..].heapify_by(compare::<i32>);
  assert_eq!(v[0], 5); // 5 is the max element
  
  v[4] = 100;
  v[..].sift_up_by(4, compare::<i32>);
  assert_eq!(v[0], 100); // 100 is the new max element
  Run this example

• fn sift_down_by<T, F>(self: &mut [T], pos: usize, f: F)

  F: CompareFunction<T>

  source

  Sifts an element down the heap until it reaches its correct position.

  This is used e.g. to restore the heap property after removing the root element. If replacing the root element with the last element of the heap, consider using sift_down_to_bottom_by instead, as it can be more efficient when the element should be close to the bottom of the heap.

  Example

  use std::collections::heap::{heapify_by, sift_down_by};
  use std::cmp::compare;
  
  let v = [1, 2, 3, 4, 5];
  v[..].heapify_by(compare::<i32>);
  assert_eq!(v[0], 5); // 5 is the max element
  
  v[0] = 3;
  v[..].sift_down_by(0, compare::<i32>);
  assert_eq!(v[0], 4); // 4 is the new max element
  Run this example

• fn sift_down_to_bottom_by<T, F>(self: &mut [T], pos: usize, f: F)

  F: CompareFunction<T>

  source

  Sifts an element at index pos to the bottom of the heap, then sifts it up until it reaches its correct position.

  This avoids extra comparisons on the way down and hence can be faster than just calling sift_down_by until the element reaches the correct position when the element is known to have to be near the bottom of the heap.

  Example

  use std::collections::heap::{heapify_by, sift_down_to_bottom_by};
  use std::cmp::compare;
  use std::mem::swap;
  
  let v = [1, 2, 3, 4, 5].as_slice_mut();
  v.heapify_by(compare::<i32>);
  
  swap(&v[0], &v[4]);
  v = v[..4]; // remove the last element
  
  v.sift_down_to_bottom_by(0, compare::<i32>);
  assert_eq!(v[0], 4); // 4 is the new max element
  Run this example