Last active
August 29, 2015 14:07
-
-
Save kevinmichaelchen/0acd2d570522e2225001 to your computer and use it in GitHub Desktop.
Detect if the max heap property is violated in a binary tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/ruby | |
# Detect if property of max heap is violated. | |
# Heap is a tree-based data structure. | |
# Here we use a binary tree. | |
# Must be monotonically decreasing from parent to child. | |
class Node | |
def initialize(value, left, right) | |
@value = value | |
@left = left | |
@right = right | |
end | |
attr_reader :value, :left, :right | |
end | |
def hasMaxHeapProperty(node) | |
# return false if the left CHILD or left SUBTREE is messed up | |
return false if !node.left.nil? && | |
(node.left.value > node.value || | |
!hasMaxHeapProperty(node.left)) | |
# return false if the right CHILD or right SUBTREE is messed up | |
return false if !node.right.nil? && | |
(node.right.value > node.value || | |
!hasMaxHeapProperty(node.right)) | |
# if neither child nor subtree is messed up, we're good | |
return true | |
end | |
n = Node.new(5, | |
Node.new(6, | |
Node.new(9, nil, nil), | |
nil), | |
Node.new(7, | |
Node.new(35, nil, nil), | |
Node.new(42, nil, nil)) | |
) | |
n2 = Node.new(5, nil, Node.new(6, nil, nil)) | |
n3 = Node.new(6, nil, Node.new(6, nil, nil)) | |
if hasMaxHeapProperty(n3) | |
puts "Okay" | |
else | |
puts "Not okay" | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment