armcburney/ruby-ds

Common algorithms and data structures written in Ruby.

Purpose

This repository provides the implementation of various algorithms in Ruby. The purpose of this repository is to re-acquaint myself with various algorithms used in computer science, as well as their spacial and time complexities.

Data Structures

Binary Tree

insert

Recursively inserts a new node into the tree.

Time complexity:
  O(n) worst case
  O(log(n)) average case

@param [Algorithms::Node] node
@param [Algorithms::Node] curr

delete

Recursively deletes a node if it exists in the tree.

Time complexity:
  O(n) worst case
  O(log(n)) average case

@param [Algorithms::Node] node

find_node

Finds and returns a node with the value in a subtree.

Time complexity:
  O(n) worst case
  O(log(n)) average case

@param [Integer] val
@param [Algorithms::Node] node
@return [Algorithms::Node]

height

Returns the height of the tree.

Time complexity:
  O(n) worst case
  O(log(n)) average case

@param [Algorithms::Node] node
@param [Integer] h
@return [Integer]

find_min

Finds and returns the minimum element in a subtree.

Time complexity:
  O(n) worst case
  O(log(n)) average case

@param [Algorithms::Node] node
@return [Algorithms::Node]

find_max

Finds and returns the maximum element in a subtree.

Time complexity:
  O(n) worst case
  O(log(n)) average case

@param [Algorithms::Node] node
@return [Algorithms::Node]

next_highest_node

Finds and returns the next highest node in a subtree.

Time complexity:
  O(n) worst case
  O(log(n)) average case

@param [Algorithms::Node] node
@return [Algorithms::Node]

count_nodes

Returns the number of nodes beneath a given node.

Time complexity:
  O(n) worst case
  O(n) average case

@param [Algorithms::Node] node
@return [Integer]

exists?

Returns `true` if the value exists in the binary subtree.

Time complexity:
  O(n) worst case
  O(log(n)) average case

@param [Algorithms::Node] node

valid?

Returns `true` if the binary subtree is valid.

Time complexity:
  O(n) worst case
  O(n) average case

@param [Algorithms::Node] node
@return [Boolean]

pre_order_traversal

Prints the tree node values pre-order.

Time complexity:
  O(n) worst case
  O(n) average case

@param [Algorithms::Node] node

in_order_traversal

Prints the tree node values in-order.

Time complexity:
  O(n) worst case
  O(n) average case

@param [Algorithms::Node] node

post_order_traversal

Prints the tree node values post-order.

Time complexity:
  O(n) worst case
  O(n) average case

@param [Algorithms::Node] node

Min Heap

insert

Inserts an element into the heap.

Time complexity:
  O(log(n)) worst case
  O(log(n)) best case

@param [Integer] val

delete_min

Deletes the minimum element from the heap.

Time complexity:
  O(log(n)) worst case
  O(log(n)) best case

@return [Integer]

min

Returns the minimum element of the heap.

Time complexity:
  O(1) worst case
  O(1) best case

@return [Integer]

size

Returns the size of the heap.

Time complexity:
  O(1) worst case
  O(1) best case

@return [Integer]

height

Returns the height of the heap.

Time complexity:
  O(1) worst case
  O(1) best case

@return [Integer]

empty?

Returns `true` if the heap is empty.

Time complexity:
  O(1) worst case
  O(1) best case

@return [Boolean]

self.decreasing_order_sort

Sorts an array using heap sort, in decreasing order.

Time complexity:
  O(n * log(n)) worst case
  O(n * log(n)) average case
  O(n) best case

@param  [Array[Integer]] arr
@return [Array[Integer]]

Max Heap

insert

delete_max

max

size

height

empty?

self.increasing_order_sort