Transcript heaps-and-graphs

Heaps
Chapter 6
Section 6.9
 A particular kind of binary tree, called a heap
 It has two properties:
1. The value of each node is greater(max heap)/less (min heap)
than or equal to the value stored in each of its children.
2. The tree is perfectly balanced, and the leaves in the last
level are all in the leftmost positions.
 Heaps can be implemented by arrays.
 Elements in a heap are not perfectly ordered. There is no
relation between siblings .
Example: the array [2 8 6 1 10 15 3 12 11] seen as a tree
Different heaps constructed with the same elements
6.9.1 Heaps as Priority Queues
 A heap is a way to implement priority queues.
 Using linked list to implement priority queue is ineffective with large
number of nodes .
 Heap is perfectly balanced tree, so reaching a leaf requires less searches.
 Two procedures has to be implemented :
1. Enqueue an element : the element is added at the end of the
heap as the last leaf .
2. Dequeue an element : remove the root element from
the heap. Why ?
Chapter 8
Graphs
 Even though trees are flexible and have many applications,
they have one limitation:
 They can only represent relations of hierarchical type, such as
relations between parent and child.
 Other relations are only represented indirectly.
 Graph, a generalization of a tree, is a data structure that
contain a collection of vertices( or nodes) and the
connections between them.
Terminology
 Graph
 collection of nodes (vertices)
 collection of line segments connecting vertices (edges)
 Graph
 Directed
 Each line segment has a direction (Arc)
 Undirected
 No direction on any line segment (Edge)
 Neighbors
 Two vertices are said to be neighbors if an edge directly
connects them
 Path
 A sequence of vertices in which each vertex is adjacent to
the other
 Cycle
 A path that start and ends with the same vertex
 Loop
 A single Arc that begins and ends with the same vertex
 Connected Graph
 There is a path from any vertex to any other vertex
 Vertex Degree
 Indegree
 Number of arcs entering the vertex
 Outdegree
 Number of arcs leaving the vertex
Storage Structures
 Two sets
 Vertices
 Edges
 Two Representations
 Arrays (Adjacency Matrix)
 Linked Lists (Adjacency List)