testheap.rb

二叉树详细源码

require 'Heap'
require 'test/unit'

class TestHeap < Test::Unit::TestCase
  def test_left()
    a = [11,22,33,44,55]
    a.base_index = 1
    assert_equal(22, a[left(1)])
  end
  
  def test_parent()
    assert_equal(0, parent(0))
    assert_equal(0, parent(1))
    assert_equal(1, parent(2))
    assert_equal(1, parent(3))
    assert_equal(2, parent(4))
    assert_equal(2, parent(5))
    assert_equal(3, parent(6))
  end
  
  
  def test_leftest?()
    assert_equal(true, leftest?(1))
    assert_equal(true, leftest?(2))
    assert_equal(false, leftest?(3))
    assert_equal(true, leftest?(4))
    assert_equal(false, leftest?(5))
    assert_equal(false, leftest?(6))
    assert_equal(false, leftest?(7))
    assert_equal(true, leftest?(8))
    assert_equal(false, leftest?(9))
    
    assert_equal(false, leftest?(0))
    assert_equal(false, leftest?(-1))
  end
  
  def test_heap_height()
    assert_equal(0, [1].heap_height)
    assert_equal(1, [1,2].heap_height)
    assert_equal(1, [1,2,3].heap_height)
    assert_equal(2, [1,2,3,4].heap_height)
    assert_equal(2, [1,2,3,4,5].heap_height)
    assert_equal(2, [1,2,3,4,5,6].heap_height)
    assert_equal(2, [1,2,3,4,5,6,7].heap_height)
    assert_equal(3, [1,2,3,4,5,6,7,8].heap_height)
    
    assert_equal(0, [].heap_height)
  end
  
  def test_heap_size()
    assert_equal(0, [].heap_size)
    assert_equal(1, [1].heap_size)
    assert_equal(2, [1,2].heap_size)
    
    a = [1,2,3]
    a.heap_size = 2
    assert_equal(2, a.heap_size)
    a << 4
    assert_equal(3, a.heap_size)
    
    b = [1,2,3]
    b.heap_size = 9
    assert_equal(3, b.heap_size)
  end
  
  def test_first_leaf()    
    assert_equal(1, ['a'].first_leaf)
    assert_equal(2, ['a','b','c'].first_leaf)
    assert_equal(3, ['a','b','c','d'].first_leaf)
    assert_equal(3, ['a','b','c','d','e'].first_leaf)
    assert_equal(4, ['a','b','c','d','e','f'].first_leaf)
    
    assert_equal(0, [].first_leaf)
  end
  
  def test_max_heapify!()
    a = [5,3,4,2,1]
    a.max_heapify!(1)
    assert_equal([5,3,4,2,1], a)
    
    assert_equal([5,3,4,2,1], [1,5,4,2,3].max_heapify!(1))
    assert_equal([5,3,4,2,1], [1,5,4,2,3].max_heapify!(1))
    assert_equal([7,5,4,2,1], [5,7,4,2,1].max_heapify!(1))
    
    assert_equal([7,5,1,2,4], [7,5,1,2,4].max_heapify!(3))
    assert_equal([7,5,3,2,4,1,2], [7,5,1,2,4,3,2].max_heapify!(3))
    
    assert_equal([7], [7].max_heapify!(1))
    assert_equal([], [].max_heapify!(1))
  end
  
  def test_max_heapify_2()
    b = [5,8,4,2,7]
    assert_equal([8,7,4,2,5], b.max_heapify!(1))
    
    b = [5,8,4,2,7]
    b.heap_size -= 1
    assert_equal([8,5,4,2,7], b.max_heapify!(1))
  end
  
  def test_max_heap!()
    assert_equal([5,4,3,1,2], [1,2,3,4,5].max_heap!)
    assert_equal([1], [1].max_heap!)
    assert_equal([2,1], [1,2].max_heap!)
    assert_equal([], [].max_heap!)
  end
  
  def test_heap_sort()
    assert_equal([1,2,3,4,5], [5,4,2,3,1].heap_sort!)
    assert_equal([1,2,3,4,5], [2,3,5,1,4].heap_sort!)
    assert_equal([1,2,2,3,3], [2,3,2,3,1].heap_sort!)
    
    assert_equal([1], [1].heap_sort!)
    assert_equal([], [].heap_sort!)
  end
  
  def test_LRMEnumerator()
    a = [11,22,33,44,55,66]
    a.extend(HeapLRMEnumerator)
    
    r = Array.new
    assert_equal([44,55,22,66,33,11], a.each() {|v| r<<v })
    assert_equal([44,55,22,66,33,11], r)
    assert_equal([11,22,33,44,55,66], a)
    
    i = Array.new
    assert_equal([44,55,22,66,33,11], a.each_index() {|v| i<<v })
    assert_equal([4,5,2,6,3,1], i)
    assert_equal([11,22,33,44,55,66], a)
  end
  
  
end