Algorithms, Part 1 Course from Princeton — Binary Tree, Binary Heaps, and Week 4 Assignment 8 puzzle

Introduction

Algorithms, Part 1 is a solid course for IT or software engineers to learn algorithms which are provided by Princeton. Of course, we still have to take time to clarify the concepts after completing the class.

Binary search tree and binary heap are fundamental data structure for storing data in the practice. In this article, we will focus on how they works.

About this Series

This series aims to wrap up contents of Algorithms, Part 1.

• week 1: Union-find and Week 1 assignment Percolation
• week 2: Stack, Queue, and Week 2 Assignment Deques and Randomized Queues
• week 3: Sorting and Week 3 assignment Collinear Points
• week 4: this article
• week 5: Hash table and Week 5 Assignment KD-Tree

Agenda

It includes the following topics in this article.

• Symbol table
• Binary search tree
• Binary heap
• Heap sort
• Immutability
• Completed code in JavaScript
• Week 4 Programming Assignment: 8 puzzle

1. Symbol Table

Key-value pair abstraction

• Insert a value with a specific key
• Given a key, search for the corresponding value

Implementations

1. sequential search in a linked list (for unordered list) -> Complexity: O(N)
2. binary search in an ordered list (when keys are comparable and we can put them in order) -> Complexity: O(Log N)

3. BST search (keep key-value pairs in the BST structure) -> Complexity: O(Log N) ~ O(N)

Performance

• The worst case is after N inserts
• The average case is after N random inserts
• Red-black tree guarantees logarithmic performance for all operations

• Ordered symbol table operations - h: height of BST (propositional to Log N if keys inserted in random order)

Related LeetCode questions

• 1870. Minimum Speed to Arrive on Time (easy)
• 200. Number of Islands (medium)
• 704. Binary Search (easy)

2. Binary Search Tree

• A BST is a “binary tree” in “symmetric order”

Binary tree

• Empty
• Two disjoint binary trees — left and right (Disjoint means that they have no nodes in common)

Symmetric order

Each node has a key, and every node’s key is

1. Larger than all keys in its left sub-tree
2. Smaller than all keys in its right sub-tree

Balanced tree

Height of complete tree with N nodes is Log N (height only increases when N is a power of 2)

1. completed binary tree - Every level of the tree is fully filled, except for perhaps the last level - To the extent that the last level is filled, it is filled left to right
2. full binary tree - Every node has either zero or two children. Node have only one child
3. perfect tree - Binary tree is both full and completed

Tree shape (depends on the order of insertion)

• Many BSTs are correspond to same set of keys
• Numbers of compares for each search/insert is equal to 1 + depth of node

Implementation in Java (from the official video)

• node class: key, value, left, right

• insert/put

• search

• delete

Ordered operation implementations

1. sub-tree count

2. rank: how many nodes < key?

3. delete the minimum

4. In-order traversal : left -> mid -> right

5. Computing the floor

6. Min

Range search

• recursively find all keys in the left tree (if any could fall in range)
• check key in current node
• recursively find all keys in the right tree (if any could fall in range)

Related LeetCode questions

• 110. Balanced Binary Tree (easy)
• 429. N-ary Tree Level Order Traversal (medium)
• 107. Binary Tree Level Order Traversal II (medium)

3. Binary Heap

Array representation of a heap-ordered complete binary tree (can use resizable array)

Heap-ordered binary tree

• keys in nodes
• parent’s key no smaller than children’s key

Array representation

• Indices start at 1
• Take nodes in level order
• No explicit links needed

Proposition

• Largest key is a[1], which is root of binary tree
• Parent of node at k is at k/2
• Children of node at k are 2k and 2k + 1

• cost

Implementation in Java (from the official video)

• Priority queue implementation with binary heap

Insertion in a heap : Child’s key becomes larger key than its parent’s key

1. Add node at end
2. Swim it up - Exchange the key in child with key in parent - Repeat until heap order restored

Cost: at most + Log N compares

Delete the maximum in a heap: parent’s key becomes smaller than one (or both) of its children’s

1. Exchange root with node at end
2. Sink it down - Exchange the key in parent with key in larger child - Repeat until heap order restored

Cost: at most + 2 Log N compares

4. Heap sort

Step 1. Heap construction

• Build heap using bottom-up method

Step 2. Sort down

• Remove the maximum, one at a time
• Leave in array, instead of nulling out

Proposition

• Use ≤ 2NlogN compares and exchanges
• Inner loop longer than quicksort’s
• Makes poor use of cache memory
• Not stable

Significance

In-place sorting algorithm with N Log N worst-case

• Merge sort: no(in-place merge possible, not practical), need extra space
• Quick sort: no(N Log N worst-case quick sort possible, not practical)
• Heap sort: yes

Implementation in Java (from the official video)

5. Immutability

• Immutable in Java: String, Integer, Double, java.io.File…
• Mutable in Java: StringBuilder, java.net.URL, arrays,…

Assumption

Client can not change keys while they’re on the PQ

Immutable data type

• Set of values and operations on those values
• Can’t change the data type value once created

Implementation of a data type in Java

Advantages

• Simplifies debugging
• Safer in presence of hostile code
• Simplifies concurrent programming
• Safe to use as key in priority queue or symbol table

Disadvantages

• Must create new object for each data type value

6. Completed code in JavaScript

• completed by myself, not from the official video

Week 4 Programming Assignment: 8 puzzle

There are two requirements.

1. board: complete APIs for the board
2. A* search algorithm: complete A* search method by using the priority queue

Requirements in detail

Solutions

• Board.java

• Solver.java

Grades

References

• [Data Structure][Tree] — Balanced Search Tree
• Binary Tree: Intro(簡介)
• Create a copy of a 2-dimensional array in Java
• 8 puzzle问题
• Getting hold of the outer class object from the inner class object

Summary

Thanks for your patient. I am Sean. I work as a software engineer.

This article is my note. Please feel free to give me advice if any mistakes. I am looking forward to your feedback.

• Subscribe me

• The Facebook page for articles

• The latest side project: Daily Learning

Related topics

How to use the two-way binding in Knout.js and ReactJS?

Learn how to use SignalR to build a chatroom application

My reflection of :

IT & Network: