heap.rb

二叉树详细源码

require 'RangeExtension'
require 'dynimic_base_index'
require 'string_extension'
require 'pp'

# Regards Array as Heap. A heap is a tree, every node has two children or less.
class Array
  # Returns index of first leaf node in the tree. Equals to heap_size/2+1
  # Example
  #    - ['a','b','c'].first_leaf         #=> 2
  #    - ['a','b','c','d'].first_leaf     #=> 3
  #    - ['a','b','c','d','e'].first_leaf #=> 3
  #    - []                           #=> 0
  def first_leaf()
    return 0 if heap_size == 0
    
    a = self
    original_base_index = a.base_index
    a.base_index = 1
    
    result = heap_size / 2 + 1
    
    a.base_index = original_base_index
    return result
  end
  
  # Returns the heap height. Returns 0 if the heap is empty.
  # Example
  #    [1].heap_height  #=> 0
  #    [1,2].heap_height  #=> 1
  #    [1,2,3].heap_height  #=> 1
  #    [1,2,3,4].heap_height  #=> 2
  #    [1,2,3,4,5].heap_height  #=> 2
  #    [1,2,3,4,5,6].heap_height  #=> 2
  #    [1,2,3,4,5,6,7].heap_height  #=> 2
  #    [1,2,3,4,5,6,7,8].heap_height  #=> 3
  #    [].heap_height  #=> 0
  def heap_height()
    return 0 if self.empty?
    return (Math::log(self.length)/Math::log(2)).floor
  end
  
  # Returns size of heap. 
  # self.heap_size equals to self.length at beginning, you can set the self.heap_size
  # a Fixnum less than self.length.
  # Example
  #    a = [1,2,3]
  #    a.heap_size  #=> 3
  #    a.heap_size = 2
  #    a << 4  #=> [1,2,3,4]
  #    a.heap_size  #=> 3
  #
  #    a.heap_size = 9
  #    a.heap_size  #=> 4  the self.heap_size never more than self.length
  def heap_size()
    return self.length if @heap_size_less_than_array_length == nil || @heap_size_less_than_array_length < 0
    return self.length - @heap_size_less_than_array_length
  end
  
  def heap_size=(arg)
    @heap_size_less_than_array_length = self.length - arg
  end
  
  def heap_string(space='  ')
    # Prepares out_heap
    # The out_heap is a full tree and every node is a String
    out_heap = Array.new
    out_heap.base_index = 1
    
    self.each do |v|
      out_heap << v.to_s
    end
    
    full_tree_size = 2**(self.heap_height+1)-1
    out_heap += Array.new(full_tree_size-out_heap.length, ' ')
    out_heap.heap_size = self.heap_size
    
    # Adds spaces to each node in out_heap
    out_heap.extend(HeapLRMEnumerator)
    out_heap.each_index(1, out_heap.length) do |i|
      l = left(i)
      r = right(i)
      
      if l > out_heap.length # is leaf
        out_heap[i] = space + out_heap[i] + space
      elsif l <= out_heap.length # is not leaf
        out_heap[i] = out_heap[i].center(out_heap[l].length+out_heap[r].length)
      end
    end
    
    # Generates "/" and "\"
    out_heap = out_heap.dup  # back to ordered enumerator
    out_heap.base_index = 1
    
    conn_lines = Array.new
    (1..out_heap.length).each do |i|
      l = left(i)
      r = right(i)
      conn_line_string = ""
      if l <= out_heap.heap_size  # has left child
        conn_line_string << "/"
      end
      if r <= out_heap.heap_size  # has right chile
        conn_line_string << "\\"
      end
      conn_lines[i] = conn_line_string.distribute_center(out_heap[i].length)
    end
    
    # Combine out_heap and conn_lines
    out_heap.each_index do |i|
      parent = parent(i)
      
      if parent >= 1 && leftest?(i)  # is leftest and is not root
        conn_lines_string = ""
        (parent...i).each do |j|
          conn_lines_string << (conn_lines[j] || "")
        end
      
        out_heap[i] = "\n" + conn_lines_string + "\n" + out_heap[i]
      end
    end
    
    return out_heap.to_s
  end
  
  # Builds max-heapify on a substree rooted at given place of node in place.
  def max_heapify!(i)
    a = self
    original_base_index = a.base_index
    a.base_index = 1
    
    l = left(i)
    r = right(i)
    
    if  l <= a.heap_size && a[i] < a[l]
      max = l
    else 
      max = i
    end
    
    if r <= a.heap_size && a[max] < a[r]
      max = r
    end
    
    if a[max] != a[i]
      a[max],a[i] = a[i], a[max]  # do exchange a[max]<->a[i]
      max_heapify!(max)
    end
    
    a.base_index = original_base_index
    return self  
  end
  
  # Builds max heap in place.
  def max_heap!()
    a = self
    original_base_index = a.base_index
    a.base_index = 1
    
    i = a.first_leaf
    i -= 1
    while(i >= 1)
      a.max_heapify!(i)
      i -= 1
    end
  
    a.base_index = original_base_index
    return self
  end
  
  # Sorts the array using heap sort algorithm in place.
  def heap_sort!()
    a = self
    original_base_index = a.base_index
    a.base_index = 1
    
    a.max_heap!
    
    (2..a.heap_size).reach do |i|
      a[1],a[heap_size] = a[heap_size], a[1]  # do exchange a[1]<->a[heap_size]
      a.heap_size -= 1
      a.max_heapify!(1)
    end
    
    return self
  end
end

# Returns i*2
# Example
#    a = [11,22,33]
#    a.base_index = 1
#    l = left(1)  #=> 2
#    a[l]  #=> 22
def left(i)
  return i*2
end

# Returns i*2+1
# Example
#    a = [11,22,33]
#    a.base_index = 1
#    lr= right(1)  #=> 3
#    a[r]  #=> 33
def right(i)
  return i*2+1
end

# Returns i/2, the index of parent of node i 
# Example
#    - parent(0)  #=> 0
#    - parent(1)  #=> 0
#    - parent(2)  #=> 1
#    - parent(3)  #=> 1
#    - parent(4)  #=> 2
#    - parent(5)  #=> 2
#    - parent(6)  #=> 3
def parent(i)
  return i/2
end

# Returns true if i is the index of leftest node of the row of tree.
# Returns false if i <= 0
# Example
#    leftest?(1)  # true
#    leftest?(2)  # true
#    leftest?(3)  # false
#    leftest?(4)  # true
#    leftest?(5)  # false
#    leftest?(6)  # false
#    leftest?(7)  # false
#    leftest?(8)  # true
#    leftest?(9)  # false
#
#    leftest?(0)  # false
#    leftest?(-1)  # false
def leftest?(i)
  return false if i<=0
  
  f = Math::log(i)/Math::log(2)
  return f == f.floor
end

module HeapLRMEnumerator
  # Returns a new array in Left-Right-Midlle order
  # Calls block once for each element in self, passing that element as a parameter.
  # Optional parameter: start_index=1, end_index=self.heap_size. 
  def each(start_index=1, end_index=self.heap_size, &action)
    return do_each(start_index, end_index, :access_value, &action)
  end
  
  # Same as Array#each, but passes the index of the element instead of the element itself.
  # The starting index at 1
  def each_index(start_index=1, end_index=self.heap_size, &action)
    return do_each(start_index, end_index, :access_index, &action)
  end
  
  private 
  
  # Returns a new array in Left-Right-Midlle order
  # Calls block once for each element or index in self, passing that element or index as a parameter.
  # Optional parameter: start_index=1, end_index=self.heap_size. 
  def do_each(start_index, end_index, access_mode, &action)
    a = self
    original_base_index = a.base_index
    a.base_index = 1
    
    target = a[start_index..end_index]
    target.base_index = 1
    
    result = Array.new
    result.base_index = 1
    logged_action = lambda do |v| 
      if access_mode == :access_value 
        result << v
      elsif access_mode == :access_index
        result << target[v]
      else
        raise "access_mode must be :access_value or :access_index"
      end
      
      action.call(v) 
      
    end
    
    lrm_access(target, start_index, end_index, access_mode, &logged_action)
   
    a.base_index = original_base_index
    return result
  end
  
  # access_mode specifed access value or index, 
  # it would be :access_value or :access_index
  def lrm_access(a, i, end_index, access_mode, &action)
    l = left(i)
    r = right(i)
    if l <= end_index
      lrm_access(a, l, end_index, access_mode, &action)
    end
    
    if r <= end_index
      lrm_access(a, r, end_index, access_mode, &action)
    end
    
    if access_mode == :access_value 
      action.call(a[i])
    elsif access_mode == :access_index
      action.call(i)
    else
      raise "access_mode must be :access_value or :access_index"
    end
  end
end

puts
a = ['A[1]','A[2] he he he he he he he he he','A[3]','A[4]','A[5]','A[6]']

puts a.heap_string()