ADT Lecture 2

Abstract Data Type vs. Data Structure

  • Set is an abstract data type which is collection of unique items.
  • Set can be written using array or sorted array data structure.
  • Sorted array implementation of set is more efficient (i.e. use less time to run) in some operations
  • So we can say that some data structures are more efficient in certain operations than others to implement the same abstract data type

Data Structure & Algorithms

  • Algorithm utilize data structures
  • Example of operations are
  • Insertion
  • Deletion
  • Search

Sorting problem

Suppose we have a list of 6 5 3 1 8 7 2 4 (in arbitrary order) and we would like to sort the list in descending (largest to smallest) order.

  • This example use list abstraction to represent the numbers as it allows duplicated elements

Array

  • We can use array data structure to implement list abstraction
  • We then apply bubble sort to the array

.

Original:       6 5 3 1 8 7 2 4
Compare 6 to 5: 6 5 3 1 8 7 2 4
Compare 5 to 3: 6 5 3 1 8 7 2 4
Compare 3 to 1: 6 5 3 1 8 7 2 4
Compare 1 to 8: 6 5 3 8 1 7 2 4
Compare 1 to 7: 6 5 3 8 7 1 2 4
Compare 1 to 2: 6 5 3 8 7 2 1 4
Compare 1 to 4: 6 5 3 8 7 2 4 1
Now 1 is sorted and can be ignored
Round 2:        6 5 3 8 7 2 4 1
Compare 6 to 5: 6 5 3 8 7 2 4 1
Compare 5 to 3: 6 5 3 8 7 2 4 1
Compare 3 to 8: 6 5 8 3 7 2 4 1
Compare 3 to 7: 6 5 8 7 3 2 4 1
Compare 3 to 2: 6 5 8 7 3 2 4 1
Compare 2 to 4: 6 5 8 7 3 4 2 1
Now 1, 2 are sorted and can be ignored

Using bubble sort the list can be sorted n rounds to sort a list with n elements. We can see that bubble sort is inefficient solution.

Heap

  • Heap is a complete binary tree (except for the bottommost level)
  • The root must be greater than the children

List: 6 5 3 1 8 7 2 4

Building a binary tree

      6
     / \
    5   3
   / \  | \
  1   8 <-- Cannot be inserted (root must be greater than children), perform bubble operation

      6
     / \
    8  <-- Still not valid
   / \
  1   5

    8
   / \
  6   3
 / \  | \
1   5 7 <-- Swap

    8
   / \
  6   7
 / \  | \
1   5 3  2
|
4 <-- Swap

    8           Completed tree
   / \
  6   7
 / \  | \
4   5 3  2
|
1

After we built a tree we can read out the values by pulling the root element one by one, replacing it by the bottommost item then correcting the result to be a valid heap

    .           Sorted: 8
   / \
  6   7
 / \  | \
4   5 3  2
|
1

    1  <-- Cut out the bottommost item* to root and perform
   / \     heap correction
  6   7
 / \  | \
4   5 3  2

* Item can be selected at random as it will be pushed back later

Heap correction:

    7           Sorted: 8
   / \
  6   1
 / \  | \
4   5 3  2

    7           Sorted: 8 7
   / \
  6   3
 / \  | \
4   5 1  2  <-- Cut off 7 and select 2 to be the next root

    6           Sorted: 8 7 6 ...
   / \
  5   3
 / \   \
4   2   1

The heap algorithm is faster as a list of a million items can be represented by a tree with around 20 levels. (220 = 1,048,576 items in full binary tree of 20 levels)