Data Structure - Githubissues

ericltw commented 4 years ago

Introduction

What is Data Structure

解決問題的數據組織。

What is Algorithm

解決特定問題的系統方法，為計算過程的本質。

What is Program

用某種程式語言實現算法。

Types of Data Structure

資料結構分為兩種類型，primitive DS, Non-Primitive DS

Primitive
- Integer
- Float
- Character
- Boolean
Non-Primitive（基於primitive）
- Physical
- Array
- Linked List
- Logical（基於physical）
- Stack
- Queue
- Tree
- Graph

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Recursion

Properties

同樣的操作以不同的輸入執行多次。
在每一步中，都嘗試把問題變小。
需要一個條件讓系統得知需停止recursion。

Why we need recursion

與iterative相比，更易於編寫代碼。
大量用於data structure，ex: tree, graphs。
大量用於"Divide and Conquer", "Greedy", "Dynamic Programming"。

Format of a 'Recursive Function'

Recursive Case - continue recursion case
Base Case - stop recursion case

SampleRecursion (parameter) {
    if (base case satisfied) {
        return some base value
    } else {
        SampleRecursion(modified parameter)
    }
}

Recursion vs Iteration

	Recursion	iteration
Space efficient	No (system stack)	Yes
Time efficient	No (system stack, some push, pop operation)	Yes
Ease of code	Yes	No

When to Use Recursion

可以將問題分解為類似的子問題時。
可以接受額外的開銷（time, space）時。
快速得到一個解決方案，而不是高效的解決方案。

如上方的其一條件不成立，則避免使用recursion。

Practical Uses of Recurision

Stack
Tree - Traversal / Searching / Insertion / Deletion
Sorting - Quick Sort / Merge Sort
Divide and Conquer
Dynamic Programming

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Algorithm Run Time Analysis

背景

算法的運行時間基於

single or multi processor
read / write speed to memory
32 bit / 64 bit
input

Intro

透過對算法的輸入大小增加，排除其他因素，量化算法運行所花費的時間。

演算法有多快不是以秒衡量，是以步驟次數。

Why we need

判別給定算法的效率。

Asymptotic Bounding

介紹

用於表示演算法時間複雜度的方式。

Big-O

介紹

為一個演算法的時間複雜度的增長上限。

定義

f(n) is O(g(n)), if for some positive constants c and k, f(n) <= c * g(n) whenever n > k.

Big Omega

介紹

為一個演算法時間複雜度的增長下界。

定義

f(n) belongs to Ω(g(n)), if for some positive constants c and k, f(n) is >= c * g(n) whenever n > k.

Theta

介紹

同時為一個演算法時間複雜度的增長上限與下界。

定義

f(n) is Θ(g(n)), if for some positive constants c1, c2 and k, c1 g(n) <= f(n) and f(n) <= c2g(n) whenever n > k.

so f(n) is Θ(g(n)) 代表 f(n) is O(g(n)) and f(n) is Ω(g(n)).

Reference

Algorithm Analysis & Time Complexity Simplified

https://medium.com/@randerson112358/algorithm-analysis-time-complexity-simplified-cd39a81fec71
Asymptotic Bounding 101: Big O, Big Omega, & Theta

https://www.youtube.com/watch?v=0oDAlMwTrLo
https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Array

Property

array可以儲存特定類型的數據
具有連續的memory分配
array中的每一個cell，都有唯一的index
index從0開始
array大小需要強制指定，不能修改

Definition

array是element的集合，每個element都由index所標識，這樣每個element的位置都可以透過index計算出來。

Types of Array

One Dimensional
Multi Dimensional

How is Array Represented in Memory

One Dimensional
- Arr[col]
- Arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- store in RAM: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
2 Dimensional
- Arr[col] [row]
- Arr[5] [2] = {{00, 10}, {20, 30}, {40, 50}, {60, 70}, {80, 90}}
- store in RAM: | 00 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
3 Dimensional
- Arr[width] [row] [col]
- Arr[2] [3] [3] = {{{11, 12, 13}, {15, 16, 17}, {19, 20, 21}}, {{23, 24, 25}, {27, 28, 29}, {31, 32, 33}}}
- store in RAM: | 11 | 12 | 13 | 15 | 16 | 17 | 19 | 20 | 21 | 23 | 24 | 25 | 27 | 28 | 29 | 31 | 32 | 33 |

Create an 1D Array

流程

Declare
1. 創建array的reference，尚未為array分配任何memory location。
Instantiation of an Array
1. compiler為array分配memory location。
2. 在reference variable儲存array第一個cell的memory address。
Initialization
1. 將值分配給array cell。

Time / Space Complexity of 1D Array

	Time Complexity	Space Complexity
Create an empty Array	O(1)	O(n) //
Insert a value	O(1)	O(1)
Traversing a given Array	O(n)	O(1)
Accessing given cell	O(1)	O(1)
Searching a given value	O(n)	O(1)
Deleting a given cell's value	O(1)	O(1)

Time / Space Complexity of 2D Array

	Time Complexity	Space Complexity
Create an empty Array	O(1)	O(mn)
Insert a value	O(1)	O(1)
Traversing a given Array	O(mn)	O(1)
Accessing given cell	O(1)	O(1)
Searching a given value	O(mn)	O(1)
Deleting a given cell's value	O(1)	O(1)

When to Use Array

需要儲存多個相同類型的數據
經常random access

When to Avoid Array

儲存的數據為不同類型
事先不知道儲存數據的數量

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Linked List

What is Linked List

為linear的資料結構，element是單獨的object。每個element（node）包含兩個item，data和下一個node的reference。linked list的重要特性是其大小是可變的。

linear data structure

element以線性的方式組織，element一個接一個地連接。traversing of data很容易，可以一次性順序地訪問所有數據（traversed in a single run），如array, linked list, stack, queue。

non-linear data structure

element不是以線性方式組織。不能一次性順序地訪問所有數據（traversed in a single run）, 如：graph, tree。

Linked List vs Array

	array	linked list
separate object	no	yes
change variable size	no	yes
random access	yes	no

Components of Linked List

Node

包含data和下一個node的reference。
Head

儲存第一個node的reference。
Tail

儲存最後一個node的reference，目的是將node插入list的尾端，運行時間為O(1)。

Type of Linked List

Single Linked List

每個node都儲存data和下一個node的reference，不儲存前一個node的reference。
Circular Single Linked List

與single linked list相同，但最後一個node儲存第一個node的reference。
Double Linked List

每一個node都儲存data, 下一個和前一個node的reference。
Circular Double Linked List

與double linked list相同，但最後一個node儲存第一個node的reference，第一個node儲存最後一個node的reference。

Why so many Types of Linked List

Single Linked List

最基礎的linked list類型，提供add / remove node的彈性。
Circular Single Linked List
- 當想要無限地loop through the list。
- ex: 多人棋盤遊戲，跟蹤玩家的回合。
Double Linked List
- 當有雙向移動的需求。
- ex: music player which has next and prev buttons.
Circular Double Linked List
- 當想要無限地雙向loop through the list。
- ex: 瀏覽器的tab切換。

How is Linked List Represented in Memory

對比於array，linked list的儲存並非儲存在連續的記憶體位置，每個node分散在記憶體各處，透過node儲存的reference彼此連結。

Single of Linked List

Creation

create head和tail指向null。
create blank node，將值插入node，reference為null。
將head, tail reference指向node。

Insertion

Insert at start of linked list
- create new node，將值插入node，reference為第一個node。
- head指向new node。
Insert at end of linked list
- create new node，將值插入node，reference為null。
- 將最後一個node指向new node。
- 將tail指向new node。
Inset at a specified location of linked list
- create new node，將值插入node，reference為null。
- 透過loop尋找插入new node的位置（ex: node3 / node4中間）。
- 將new node指向node4。
- 將node3指向new node。

Traversal

loop from head to tail.

Search a value

loop from head to tail.

Deletion of node

Delete first node
- list只有一個node
- 將head, tail設為null。
- list有多個node
- 將head指向node2。
Delete last node
- list只有一個node
- 將head, tail設為null。
- list有多個node
- 透過loop尋找倒數第二個node。
- 將tail指向倒數第二個node。
Delete any node apart from above 2
- 透過node尋找預刪除的node（node4）。
- 將node3指向node5。

Delete the Entire Single Linked List

將head, tail設為null。

Time Complexity

	Time Complexity	Space Complexity
Creation (one node)	O(1)	O(1)
Insertion	O(n)	O(1)
Searching	O(n)	O(1)
Traversing	O(n)	O(1)
Deletion of a node	O(n)	O(1)
Deletion of linked list	O(1)	O(1)

Circular Single Linked List

Time Complexity

	Time Complexity	Space Complexity
Creation (one node)	O(1)	O(1)
Insertion	O(n)	O(1)
Traversing	O(n)	O(1)
Searching	O(n)	O(1)
Deletion of a node	O(n)	O(1)
Deletion of linked list	O(1)	O(1)

Double Linked List

Time Complexity

	Time Complexity	Space Complexity
Creation (one node)	O(1)	O(1)
Insertion	O(n)	O(1)
Traversing	O(n)	O(1)
Searching	O(n)	O(1)
Deletion of a node	O(n)	O(1)
Deletion of linked list	O(n)	O(1)

Circular Double Linked List

Time Complexity

	Time Complexity	Space Complexity
Creation (one node)	O(1)	O(1)
Insertion	O(n)	O(1)
Traversing	O(n)	O(1)
Searching	O(n)	O(1)
Deletion of a node	O(n)	O(1)
Deletion of linked list	O(n)	O(1)

Time Complexity (Array vs Linked List)

	Array	Linked List
Create (empty array / one node)	O(1)	O(1)
Insertion at 1st position	O(1)	O(1)
Insertion at last position	O(1)	O(1)
Insertion at nth position	O(1)	O(n)
Delete from 1st position	O(1)	O(1)
Delete from last position	O(1)	O(n) / O(1)
Delete from nth position	O(1)	O(n)
Searching in unsorted data	O(n)	O(n)
Searching in sorted data	O(log n)	O(n)
Accessing nth element	O(1)	O(n)
Traversing	O(n)	O(n)
Deleting entire array / linked list	O(1)	O(1) / O(n)

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Stack

Property of Stack

遵循LIFO (Last in First out) method。

Why We Need Stack

當創建一個利用"後進先出"的應用程序時。
EX: browser中的back button。

Common Operatios

CreateStack
Push
Pop
Peek

返回last value of stack，但不會取出該value。
isEmpty

返回stack是否為空。
isFull

與isEmpty相反（topOfStack == arr.size）。
DeleteStack

Implementation Options of Stack

Array
- Pros
  - easy to implement
- Cons
  - Fixed Size
Linked List
- Pros
  - variable size
- Cons
  - moderate to implement

Array Implementation

Time Complexity

	Time Complexity	Space Complexity
Create Stack	O(1)	O(n)
Push	O(1)	O(1)
Pop	O(1)	O(1)
Peek	O(1)	O(1)
isEmpty	O(1)	O(1)
isFull	O(1)	O(1)
Delete Stack	O(1)	O(1)

Linked List Implementation

Time Complexity

	Time Complexity	Space Complexity
Create Stack	O(1)	O(1)
Push	O(1)	O(1)
Pop	O(1)	O(1)
Peek	O(1)	O(1)
isEmpty	O(1)	O(1)
Delete Stack	O(1)	O(1)

When to Use

Helps manage the data in particular way (LIFO).
Cannot be easily corrupted (cannot insert data in middle).

When to Avoid

Random access not possible.

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Queue

Property of Queue

遵循FIFO (First in First Out) method。

Why we Need Queue

當創建一個利用"先進先出"的應用程序時。
EX: job scheduling (FIFO)

Common Operations

createQueue
enQueue
deQueue
peekInQueue
isEmpty
isFull
deleteQueue

Implementation Options of Queue

Array
- Linear Queue
- Circular Queue
Linked List
- Linear Queue

Array Implementation (linear queue)

Time Complexity

	Time Complexity	Space Complexity
CreateQueue	O(1)	O(n)
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
Peek	O(1)	O(1)
isEmpty	O(1)	O(1)
isFull	O(1)	O(1)
DeleteQueue	O(1)	O(1)

Array Implementation (circular queue)

Why Circular Queue

deQueue的操作造成blank cell linear queue (array implementation).

Time Complexity

	Time Complexity	Space Complexity
CreateQueue	O(1)	O(n)
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
Peek	O(1)	O(1)
isEmpty	O(1)	O(1)
isFull	O(1)	O(1)
DeleteQueue	O(1)	O(1)

Linked List Implementation (linear queue)

Time Complexity

	Time Complexity	Space Complexity
CreateQueue	O(1)	O(1)
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
Peek	O(1)	O(1)
isEmpty	O(1)	O(1)
DeleteQueue	O(1)	O(1)

Array vs Linked List Implementation

linked list對比array更佳節省空間（不須事先宣告），且不會有滿空間的情況。

When to Use

Helps manage the data in particular way (FIFO).
Not easy corrupted (cannot insert data in middle).

When to Avoid

Random access is not possible.

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Binary Tree

Properties of Tree

用於分層形式表示數據。
每個node都有兩個組成成份，data和reference。
有一個root node，和兩個不相交的binary tree，left subtree和right subtree。

Why We Need Tree

linked list對比array更節省空間，但在insertion, deletion增加了運算時間，時間複雜度由O(1) 變為O(n)，searching的時間複雜度也維持於O(n)。tree的目的解決linked list insertion, deletion, 和searching時間複雜度的問題。

Tree Terminologies

Root

沒有parent的node。
Edge

同時連結parent和child的node。
Leaf

沒有children的node。
Sibling

兩個children擁有同一個parent。
Ancestor

指的是某個node的parent, grand-Parent...
Depth of Node

從root到node的path length。
Height of Node

從deepest node到node的path length。
Height of Tree

與height of root node相同。
Depth of Tree

與depth of root node相同。
Predecessor

immediate previous node in inorder traversal of the binary tree.
Successor

immediate next node in inorder traversal of the binary tree.

What is Binary Tree

在一個tree中的每個node都具有0, 1或2個child時，這個tree被稱為binary tree。
為一個data structure family (BST, Heap tree, AVL, Red-Black, Syntax tree, Huffman Coding Tree, etc..)。

Why we need learn Binary Tree

為一些advanced tree的基礎（BST, AVL, Red-Black, Expression Tree, etc...）。
用於解決特定的問題
- Huffman Coding
- Heap (Priority Queue)
- Expression parsing

Types of Binary Tree

Strict Binary Tree

每個node有兩個children或沒有。
Full Binary Tree

每個non-leaf node有兩個children，所有的leaf node都在同一級別。
Complete Binary Tree

除了最後一級別以外的所有級別都以完全填滿，在最後一個level，所有的key都靠左。

Tree Representation

Using Linked List
Using Array

Binary Tree - Common Operations

Creation of tree
Insertion of a node
Deletion of a node
Search for a value
Traverse all nodes
Deletion of tree

Traversing all nodes of Binary Tree (Linked-List)

Depth First Search

PreOrder Traversal

Root -> Left Subtree -> Right Subtree

preorderTraversal(root)
    if (root equals null)
        return error message
    else
        print root
        preorderTraversal(root.left)
        preorderTraversal(root.right)

InOrder Traversal

Left Subtree -> Root -> Right Subtree

inOrderTraversal(root)
    if (root equals null)
        return error message
    else
        inOrderTraversal(root.left)
        print(root)
        inOrderTraversal(root.right)

PostOrder Traversal

Left Subtree -> Right Subtree -> Root

postOrderTraversal(root)
    if (root equals null)
        return
    else
        postOrderTraversal(root.left)
        postOrderTraversal(root.right)
        print root

Breadth First Search

LevelOrder Traversal

levelOrderTraversal(root)
    Craete a Queue(Q)
    enqueue(root)
    while(Queue is not empty)
        enqueue() the child of first element
        dequeue() and print

Search for value un Binary Tree (Linked-List)

if root == null
    return error message
else
    do a level order traversal
        if value found
            return success message
    return unsuccessful message

Insert value in Binary Tree (Linked-List)

if root is blank
    insert new node at root
else
    do a level order traversal and find the first blank space
    insert in that blank place

Delete value from Binary Tree (Linked-List)

search for the node to be deleted
find deepest node in the tree
copy deepest node's data in current node
delete deepest node

Delete Binary Tree (Linked-List)

root = null;

Linked List Implementation

Time Complexity

	Time Complexity	Space Complexity
Createion of Tree (blank)	O(1)	O(1)
Insertion of value in tree	O(n)	O(n)
Deletion of value from tree	O(n)	O(n)
Searching for a value in tree	O(n)	O(n)
Traversing a tree	O(n)	O(n)
Deleting entire tree	O(1)	O(1)

Array Implementation // TODO

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Binary Search Tree (BST)

What is BST

Binary Search Tree為Binary Tree，所有的node滿足以下property:

一個node的left sub-tree中的每一個node value小於該node的value。
一個node的right sub-tree中的每一個node value大於該node的value。

Why we need BST

BST的目的是優化linked list searching, insertion, deletion的時間複雜度，由O(n)優化為O(log n)。

Common Operations of BST

Creation of BST
Search for a value
Traverse all nodes
Insertion of a node
Deletion of a node
Deletion of BST

Creation of BST

initial Root with null.

Searching in BST

BST_Search(root, value)
    if (root is null)
        return null
    else if (root == value)
        return root
    else if (value < root)
        BST_Search(root.left, value)
    else if (value > root)
        BST_Search(root.right, value)

Traversal of BST

Depth First Search
- PreOrder Traversal
- InOrder Traversal
- PostOrder Traversal
Breadth First Search
- LevelOrder Traversal

Inserting a node in BST

Cases

BST is blank.
BST is non-blank.

BST_Insert(currentNode, valueToInsert)
    if (current is null)
        create a node, insert 'valueToInsert' in it
    else if (valueToInsert <= currentNode's value)
        currentNode.right = BST_Insert(currentNode.right, valueToInsert)
    else
        currentNode.left = BST_Insert(currentNode.left, valueToInsert)
    return currentNode

Deletion of a node from BST

Cases

Node to be deleted is leaf node
Node to be deleted is having 1 child
Node to be deleted have 2 children

Cases 1 - Node to be deleted is leaf node

deleteNodeOfBST(root, valueToBeDeleted)
    if (root == null) return null;
    if (valueToBeDeleted < root's value)
        root.left = deleteNodeOfBST(root.left, valueTOBeDeleted)
    else if (valueToBeDeleted > root's value)
        root.right = deleteNodeOfBST(root.right, valueToBeDeleted)
    else //current node is the node to be deleted
        if root have both children, then find minimum element from right subtree (case#3)
            replace current node with minimum node from the right subtree and delete minimum node from right
        else if nodeToBeDeleted has only left child (case#2)
            root = root.Left()
        else if nodeToBeDeleted has only right child (case#2)
            root = root.Right()
        else root = null
    return root;

Deletion of entire BST

root = null;

Time Complexity

	Time Complexity	Space Complexity
Creation of Tree	O(1)	O(1)
Searching of Value	O(log n)	O(log n)
Traversing Tree	O(n)	O(n)
Insertion of Node	O(log n)	O(log n)
Deletion of Node	O(log n)	O(log n)
Deleting entire Tree	O(1)	O(1)

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

AVL Tree

Why learn AVL Tree

基於給定的incoming data，BST將歪斜成長，導致insertion, searching, deleting的時間複雜度從理想的O(log n)變為O(n)。AVL tree試圖解決這個問題，透過'Rotation'的概念。

What is AVL Tree

AVL tree為balanced Binary Search Tree，任何node的left subtree和right subtree高度最多相差1。如任何left subtree和right subtree高度相差超過1，都會經過rotation以恢復此屬性。empty height 被視為-1。

Common Operations of AVL Tree

Create a AVL Tree
Search a node
Traverse all nodes
Insert a node
Delete a node
Delete the AVL tree

Create a AVL Tree / Search a node / Traverse all nodes

same as binary search tree.

Insert a Node

Cases

When 'rotation' is not required
When 'rotation' is required (LL, LR, RR, RL)

Left-Left Condition

left-left node from current node is causing disbalance.
透過right rotation平衡。

rightRotate(currentDisbalancedNode)
    newRoot = currentDisbalancedNode.Left
    currentDisbalancedNode.Left =  currentDisbalancedNode.Left.Right
    newRoot.Right = currentDisbalancedNode
    currentDisbalancedNode.Height = caculateHeight(currentDisbalancedNode)
    newRoot.Height = caculateHeight(newRoot)

Left-Right Condition

left-right node from current node is causing disbalance.
透過left rotation和right rotation平衡。

leftRotate（currentDisbalancedNode'sLeftChild）
    newRoot = currentDisbalancedNode'sLeftChild.Right
    currentDisbalancedNode'sLeftChild.Right = currentDisbalancedNode'sLeftChild.Right.Left
    newRoot.left = currentDisbalancedNode'sLeftChild
    currentDisbalancedNode'sLeftChild.Height = caculateHeight(currentDisbalancedNode'sLeftChild)
    newRoot.Height = caculateHeight(newRoot)
    return newRoot;

Right-Right Condition

Right-Right Node from currentNode is causing disbalance.
透過left rotation平衡。

Right-Left Condition

Right-Left Node from currentNode is causing disbalance.
透過right rotation和left rotation平衡。

Algorithm // TODO

Deletion of node from AVL Tree

Cases

When tree does not exists
When 'rotation' is not required (BST consitions)
When 'rotation' is required (LL, LR, RR, RL)

Algorithm // TODO

Time Complexity

	Time Complexity	Space Complexity
Creation of AVL Tree	O(1)	O(1)
Insertion of node	O(log n)	O(log n)
Deletion of node	O(log n)	O(log n)
Searching a value	O(log n)	O(log n)
Traversing entire AVL Tree	O(n)	O(n)
Deleting entire AVL Tree	O(1)	O(1)

BST vs AVL

	Worst case	Worst case
	BST	AVL
Creation of Tree	O(1)	O(1)
Insertion of node	O(n)	O(log n)
Deletion of node	O(n)	O(log n)
Searching of value	O(n)	O(log n)
Traversing entire Tree	O(n)	O(n)
Deleting entire Tree	O(1)	O(1)

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview

ericltw commented 4 years ago

Binary Heap

What is Binary Heap

Binary heap為binary tree，且具有某些special properties。
- Heap properties
- 任何一個node的value均小於該node children的value（Min-Heap）。
- 任何一個node的value均大於該node children的value (Max-Heap)
- Complete Tree
- Tree中的每個level（除了最後一個level）都全部填滿，最後一個level的node均靠左。
- 可透過一維陣列實現。

Why we need Binary Heap

在一組number中找到min / max，在O(logn)的時間中完成。
插入number時，在O(logn)的時間中完成。

Types of Binary Heap

Min-Heap
Max-Heap

Common Operations

createHeap

創建blank array用於儲存heap。
peekTopOfHeap

return min / max from heap.
extractMin / extractMax

extract min / max from heap. We can extract only this node.
sizeOfHeap

return heap size.
insertValueInHeap

insert value in heap.
deleteHeap

deletes the entire heap.

Implementation Options

Array based.
Reference / Pointer based.

Insertion of Heap

insertValueInHeap(value)
    if (tree does not exist)
        return error message
    else
        insert 'value' in first unused cell of array
        sizeOfHeap ++
        heapifyBottomToTop(sizeOfHeap)

ExtractMin from Heap

extractMin()
    if (tree does not exist)
        return error message
    else
        extract 1st cell of array
        promote last element to first
        sizeOfHeap --
        heapifyTopToBottom(1)

Time & Space Complexity (array)

	Time Complexity	Space Complexity
createHeap	O(1)	O(n)
peekTopOfHeap	O(1)	O(1)
sizeOfHeap	O(1)	O(1)
insertValueInHeap	O(log n)	O(log n)
extractMin / extractMax	O(log n)	O(log n)
deleteHeap	O(1)	O(1)

Why Avoid Reference based implementaton

extractMin中取得最後一個node需要O(n)。

Reference

https://www.udemy.com/course/learn-data-structure-algorithms-with-java-interview/

ericltw / notes

Data Structure #76

Introduction

What is Data Structure

What is Algorithm

What is Program

Types of Data Structure

Reference

Recursion

Properties

Why we need recursion

Format of a 'Recursive Function'

Recursion vs Iteration

When to Use Recursion

Practical Uses of Recurision

Reference

Algorithm Run Time Analysis

背景

Intro

Why we need

Asymptotic Bounding

介紹

Big-O

介紹

定義

Big Omega

介紹

定義

Theta

介紹

定義

Reference

Array

Property

Definition

Types of Array

How is Array Represented in Memory

Create an 1D Array

流程

Time / Space Complexity of 1D Array

Time / Space Complexity of 2D Array

When to Use Array

When to Avoid Array

Reference

Linked List

What is Linked List

Linked List vs Array

Components of Linked List

Type of Linked List

Why so many Types of Linked List

How is Linked List Represented in Memory

Single of Linked List

Creation

Insertion

Traversal

Search a value

Deletion of node

Delete the Entire Single Linked List

Time Complexity

Circular Single Linked List

Time Complexity

Double Linked List

Time Complexity

Circular Double Linked List

Time Complexity

Time Complexity (Array vs Linked List)

Reference

Stack

Property of Stack

Why We Need Stack

Common Operatios

Implementation Options of Stack

Array Implementation

Time Complexity

Linked List Implementation

Time Complexity

When to Use

When to Avoid

Reference

Queue