-
Notifications
You must be signed in to change notification settings - Fork 0
Data Structures
- Boolean, true or false
- Character
- Floating-point, single-precision real number values
- Double, a wider floating-point size
- Integer, integral or fixed-precision values
- Enumerated type, a small set of uniquely named values
- Array
- Record (also called tuple or struct)
- Union
- Tagged union (also called variant, variant record, discriminated union, or disjoint union)
Definition: A Heap is a container for objects that have keys, where that key is typically a number such that you can evaluate that one key is larger than another.
Alternative Types: While the above definition is an Extract-min Heap, you could also have an Extract-Max heap (the Heap would not perform both Extrace-Min and Extrace-Max, only one or the other).
Other Names:
- Priority Queue
Example: A Heap may be a container of "event" objects where the key is the time at which the event is meant to occur.
Main Operations:
-
Insert: Add a new object to the Heap.
O(log(n))
-
Extract Minimum: Remove an object in the Heap with the minimum key value.
O(log(n))
-
Heapify: Initialize a Heap.
O(n)
- **Delete:*ased upon the key)
-
Insert: Add a new record.
O(1)
-
Delete: Delete an existing record.
O(1)
-
Lookup: Check for a particular record.
O(1)
Canonical use of Hash Table: Whenever you are needing to perform a large number of lookups, the Hash Table is going to be a huge help.
Implementation Fun Facts: Hash Tables are implemented by reducing the total number of items in your domain (the "Universe") by hashing each item, and placing the result in buckets. Your domain can be anything, such as all the names of your customers, phone numbers, etc. You hash the items in your domain, transferring those into a much smaller number of buckets which you can then access to get your specific key.
There are two main methods to avoiding collisions (two keys with the same hashed value, or bucket)
- Chaining: Having each bucket correspond to a list, where you can then just look up your key in the list.
- Having any colliding hashes instead decide to increment up the resulted hash to a non-taken hash. This implementation is generally less space-intensive, but sometimes slower and less obvious to implement.
Definition: The goal of a Binary Search Tree is to act like a Sorted Array, but have fast (logarithmic time) insertions and deletions.
For any Search Tree, for any given node, all keys that are smaller are on the left and all keys that are larger are on the right. This rule then creates the possibility for the depth of the tree to be anywhere from log(n) to n-1.
Alternative Types:
-
Balanced Binary Search Tree
- Red-Black Trees
- Bayer
- Guibes-Sedgewick
- AVL Trees, Splay Trees, B Trees
- There are also non-Binary Search Trees, often used in Databases.
Main Operations: Most of these operations are quite easy/quick due to the fact that the items are already sorted.
- Operations that are also within a Sorted Array:
-
Search (Binary Search)
O(log(n))
-
Select (based upon position "in line")
O(log(n))
-
Min/Max
O(log(n))
-
Predecessor/Successor (The next largest/smallest item)
O(log(n))
-
Rank (How many keys in the structure are <= a given number)
O(log(n))
-
Output in Sorted Order
O(n)
-
Search (Binary Search)
- Operations new to Binary Tree:
-
Insert
O(log(n))
-
Delete
O(log(n))
-
Insert
Canonical use of Binary Search Tree: The main use for a Binary Search Tree is when you want a more dynamic sorted array. The Binary Search Tree can perform all of the functionality of a Sorted Array with nearly the same efficiency, taking speed concessions for the above Operations to gain the ability for quick Inserts and Deletes.
Implementation Fun Facts: Red-Black Rules:
- Each Node is Red or Black
- Root is Black
- No 2 Reds in a row (each red node would only have black children)
- Every Root-->Null path has the same number of Black nodes. (aka, it's balanced)
Keeping this pattern true isn't too hard with a small, dynamic data set, but as more and more data pieces are added/removed, restructuring (or "rotating") will need to be performed to keep the tree perfectly balanced.
Definition: A Bloom Filter is very analogous to a Hash Table, except that it takes up considerably less space, yet has a small chance of a false-positive lookup. That is, that is can think an entry is within the Bloom Filter that has actually never been added.
Main Operations: The same as a Hash Table.
Canonical use of Bloom Filters: A common use of Bloom Filters would be disallowed-password functions, where false-positives are quite unimportant, yet space may be of major concern for such a small feature in your application.
Another very common usage in present day would be for various functions on internet routers to keep track of down-stream IP's, blocked IP's, usage statistics, and more. These routers tend to have tight space restrictions, and require very fast lookups and inserts.