Class: BinaryMinHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithm_selector.rb

Overview

MinHeap helper class for Heap Sort

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(&prc) ⇒ BinaryMinHeap

Returns a new instance of BinaryMinHeap.



592
593
594
595
 
# File 'lib/algorithm_selector.rb', line 592

def initialize(&prc)
  @store = []
  @prc = prc || Proc.new { |el1, el2| el1 <=> el2 }
end

Class Method Details

.child_indices(len, parent_index) ⇒ Object 



626
627
628
 
# File 'lib/algorithm_selector.rb', line 626

def self.child_indices(len, parent_index)
  [2 * parent_index + 1, 2 * parent_index + 2].select { |idx| idx < len }
end

.heapify_down(array, parent_idx, len = array.length, &prc) ⇒ Object 



635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
 
# File 'lib/algorithm_selector.rb', line 635

def self.heapify_down(array, parent_idx, len = array.length, &prc)
  prc ||= Proc.new { |el1, el2| el1 <=> el2 }

  left_child, right_child = child_indices(len, parent_idx)

  parent = array[parent_idx]

  children = []
  children.push(array[left_child]) if left_child
  children.push(array[right_child]) if right_child

  if children.all? { |child| prc.call(parent, child) <= 0 }
    return array
  end

  swap_idx = nil
  if children.length == 1
    swap_idx = left_child
  else
    swap_idx =
      prc.call(children[0], children[1]) == -1 ? left_child : right_child
  end

  array[parent_idx], array[swap_idx] = array[swap_idx], parent
  heapify_down(array, swap_idx, len, &prc)
end

.heapify_up(array, child_idx, len = array.length, &prc) ⇒ Object 



662
663
664
665
666
667
668
669
670
671
672
673
674
 
# File 'lib/algorithm_selector.rb', line 662

def self.heapify_up(array, child_idx, len = array.length, &prc)
  prc ||= Proc.new { |el1, el2| el1 <=> el2 }
  return array if child_idx == 0

  parent_idx = parent_index(child_idx)
  child, parent = array[child_idx], array[parent_idx]
  if prc.call(child, parent) >= 0
    return array
  else
    array[child_idx], array[parent_idx] = parent, child
    heapify_up(array, parent_idx, len, &prc)
  end
end

.parent_index(child_index) ⇒ Object 



630
631
632
633
 
# File 'lib/algorithm_selector.rb', line 630

def self.parent_index(child_index)
  raise "root has no parent" if child_index == 0
  (child_index - 1) / 2
end

Instance Method Details

#count ⇒ Object 



597
598
599
 
# File 'lib/algorithm_selector.rb', line 597

def count
  @store.length
end

#extract ⇒ Object 



601
602
603
604
605
606
607
608
609
610
 
# File 'lib/algorithm_selector.rb', line 601

def extract
  raise "no element to extract" if count == 0
  val = @store[0]
  @store.pop if count == 1
  if count > 1
    @store[0] = @store.pop
    self.class.heapify_down(@store, 0, &@prc)
  end
  val
end

#peek ⇒ Object 



612
613
614
615
 
# File 'lib/algorithm_selector.rb', line 612

def peek
  raise "no element to peek" if count == 0
  @store[0]
end

#push(val) ⇒ Object 



617
618
619
620
 
# File 'lib/algorithm_selector.rb', line 617

def push(val)
  @store.push(val)
  self.class.heapify_up(@store, count - 1, &@prc)
end