## Data Abstraction and Basic Data Structures

### Abstract Data Type(ADT)

**Abstract Data Type**

- Structures - data structure declarations
- Functions - operation definitions

**An ADT is identified as a Class**

- in languages such as C++ and Java

**Designing algorithms and proving correctness of algorithms**

- based on ADT operations and specifications

### Binary Tree ADT

A binary tree is a set of elements, called nodes, that is empty or satisfies

- There is a distinguished node called
**root** - The remaining nodes are divided into two disjoint subsets, and , each of which is a binary tree( is called left subtree and is called the right subtree of )

- There is a distinguished node called
There are most nodes at depth of a binary tree

- A binary tree with nodes has height at least
- A binary tree with height has at most nodes

### Stack

- A stack is a linear structure in which insertions and deletions are always made at one end, called top
- This updating policy is called
**last in, first out(LIFO)**

### Queue

- A queue is alinear structure in which

- all insertions are done at one end, called the or
- all deletions are done at the other end, called the

- This updating policy is called
**first in, first out(FIFO)**

### Priority Queue

- A priority queue is a structure with some aspects of
**FIFO queue**but in which element order is related to each**element’s priority**, rather than its chronological arrival time - The one element that can be inspected and removed is the most important element currently in the priority queue

### Union-Find ADT for Disjoint Sets

- Through a
`Union`

operations, two (disjoint) sets can be combined

- Let the set id of the original two set be, and
- Then, new set has one unique set id that is either or $t

- Through a
`Find`

operation, the current set id of an element can be retrieved - Often elements are integers and the set id is some particular element in the set, called the leader

#### Operations

`UnionFind create(int n)`

- create a set of singleton disjoint sets

`int find(unionFind sets, e)`

- return the set id for

`void makeSet(unionFind sets, int e)`

- union one singleton set ( not already in the sets)

`void union(unionFind sets, int s, int t)`

- and are set ids,
- a new set is created by union of set and set
- the new set id is either or , in some case
`min(s,t)`

### Dictionary ADT

- A dictionary is a general associative storage structure
- Items in a dictionary

- have an identifier
- associated information that needs to be stored and retrieved
- no order implied for identifiers in a dictionary ADT

## Sorting

### Insertion Sort

**Input**

, an array of elements, and , the number of elements. The range of indexes is

**Output**

, with elements in nondecreasing order of their keys

```
void insertionSort(Element[] E, int n)
int xindex;
for(xindex=1; xindex<n; xindex++)
Element current = E[xindex];
key x = current.key;
int xLoc = shiftVacRec(E, xindex, x);
E[xLoc] = current;
return;
================================================
int shiftVacRec(Element[] E, int vacant, Key x)
int xLoc;
if(vacant == 0)
xLoc = vacant;
else if(E[vacant-1].key <= x)
xLoc = vacant;
else
E[vacant] = E[vacant-1]
xLoc = shiftVacRec(E, vacant-1, x);
return xLoc;
```

#### sourcecode

### Quick Sort

Quick sort is a randomized sorting algorithm based on the **divde-and-conquer** paradigm

- Divde

Pick a random element (called pivot) and partition into

- elements less than
- elements equal
- elements greater than

- Conquer

sort and - Combine

join and $G

#### Partition

- Partition an input sequence as follows

- remove, in turn, each element from and
- insert into or , depending on the result of the comparison with the pivot

- Each insertion and removal is at the beginning or at the end of a sequence, and hence takes time
- Thus, the partition step of quick-sort takes time

```
Algorithm partition(S, p)
Input sequence S, position p of pivot
Output subsequences L, E, G of the elements of S less than, equal to, or greater than the pivot
L, E, G <- empty sequences
x <- S.remove(p)
while is not S.isEmpty()
y <- S.remove(S.first())
if y<x
L.insertLast(y)
else if y == x
E.insertLast(y)
else
G.insertLast(y)
return L, E, G
```

### Merge Sort

**Problem**

Given two sequences and sorted in nondecreasing order, merge them to create one sorted sequence

**Strategy**

Determine the first item in C: It is the minimum between the first items of and . Suppose it is the first item of . Then, the rest of must be the result of merging the rest of with

```
Merge(A, B, C)
if(A is empty)
rest of C = rest of B
else if(B is empty)
rest of C = rest of A
else if(first of A <= first of B)
first of C = first of A
merge(rest of A, B, rest of C)
else
first of C = first of B
merge(A, rest of B, rest of C)
return
```

**Input**

Array and indexes , and , such that the elements are defined for

**Output**

is sorted rearrangement of the same elements

```
void mergeSort(Element[] E, int first, int last)
if(first<last)
int mid = (first+last)/2
mergeSort(E, first, mid);
mergeSort(E, mid+1, last)
merge(E, first, mid, last)
```

### Heap Sort

A Heap data structure is a binary tree with special properties

**Heap Structure****Partial order tree property**

#### Heap Structure

- A binary tree is a heap structure if an only if it satisfies the following conditions()

- is complete at least through depth
- All leaves are at depth or
- All paths to a leaf of depth are to the left of all paths to a leaf of depth

- Such a tree is also called a left-complete binary tree

#### Partial order tree property

- A tree is a partial order tree if and only if the key at any node is greater than or equal to the keys at each of its children

#### Construct Heap

**Input**

A heap structure that does not necessarily have the partial order tree property

**Output**

with the same nodes rearranged to satisfy the partial order tree property

```
void constructHeap(H)
if(H is not leaf)
constructHeap(left subtree of H);
constructHeap(right subtree of H);
Element K = root(H);
fixHeap(H, K)
```

#### Sorting

`heapSort(E, n)`

// construct H from E, the set of n elements to be sorted

```
for(i=m; i>=1; i--)
curMax = getMax(H)
deleteMax(H)
E[i] = curMax;
```

`deleteMax(H)`

- copy the rightmost element of the lowest level of into
- delete the rightmost element on the lowest level of
`fixHeap(H,K)`

`fixHeap(H, K)`

```
if(H is leaf)
insert K in root(H);
else
set largerSubHeap to leftSubtree(H) or rightSubtree(H), whichever has larger key at its root. This involves one key comparison
if(K.key >= root(largerSubHeap.key))
insert K in root(H)
else
insert root(largerSubHeap) in root(H)
fixHeap(largerSubHeap, K)
return
```

### Radix sort

Properties for example

- keys are names
- keys are all five-digit decimal integers
- keys are integers between 1 and

For sorting each of these examples, the keys are

- distributed into different piles
- sort each pile individually
- combine all sorted piles

Algorithms that sort by such methods are not in the class of algorithms previously considered because

- to use them we must know something about either the structure or the range of the keys

#### Startegy

- If the keys are distributed into piles (also called buckets) first according to their least significant digits(or bits, letters, or fields)
- then the problem of sorting the buckets has been completely eliminated

#### Sorting

List radixSort(List , int , int )

```
List[] buckets = new List[radix];
int fields; // field number within the key
List newL;
for(field=0; field < numFields; field++)
Initialize buckets array to empty lists
distribute(newL, buckets, radix, field);
newL = combine(buckets, radix)
return newL;
```

void distribute(List , List[] , int , int )

```
//distribute keys into buckets
List remL;
remL = L;
while(remL is not null)
Element K = first(remL);
int b = maskShift(field, radix, K.key);
buckets[b] = cons(K, buckets[b]); //construct list
remL = rest(remL);
return
```

List combine(List[] , int )

```
//Combine linked lists in all buckets into one list L
int b;
List L, remBucket;
L = null;
for(b = radix-1; b>=0; b--)
remBucket = buckets[b];
while(remBucket is not null)
key K = first(remBucket);
L = cons(K, L)
remBucket = rest(remBucket);
return L;
```

#### 'Class' 카테고리의 다른 글

[cs224n] Lecture 4 Word Window Classification and Neural Networks (0) | 2018.03.25 |
---|---|

[cs224n] Lecture 1 Natural Language Processing with Deep Learning (0) | 2018.03.10 |

Algorithm 정리 (0) | 2015.05.08 |

computer network 정리 (0) | 2015.05.08 |

OS(Operating System) 정리 (2) | 2015.04.29 |

Data Structure, 자료구조 정리 (0) | 2015.04.18 |