Online Typing Test

Online Typing Test visit Online typing test to challenge with friends.

Click to Change language

English

Switch the language of the Typing Test

Albanian

Danish

English

German

Italian

Estonian

Croatian

Spanish

Urdu

Polish

Finnish

Czech

French

Dutch

Filipino

Greek

1:00

Visit Online typing test to challenge with friends.

Result
Words per minute (WPM)
Keystrokes	(29 | 0)
Correct words
Wrong words	0
You result is (better now, from previous result. Keep typing until become Master)

Building a Heap - Example

Building a Heap - Example

Building a max-heap from the following unsorted array results in the first heap example. i starts off as 5.

MAX-HEAPIFY  is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.

Analysis

•Simple bound:

•O(n) calls to MAX-HEAPIFY

•Each of which takes O(lg n)

•time = O(n lg n)

HEAP-SORT(A)

BUILD-MAX-HEAP(A)

for i ß length [A] downto 2

  do exchange A[1] with A[i]

        heap-size[A] ß heap-size[A] – 1

        MAX-HEAPIFY(A,1) 

HEAP-SORT - Analysis

BUILD -MAX-HEAP: O(n)

for loop: n – 1 times

exchange elements: O(1)

MAX-HEAPIFY: O(lg n)

Total time: O(n lg n).

Though heapsort is a great algorithm, a well-implemented quicksort usually beats it in practice.

Loop invariant

Loop invariant
•It is the formal relationship between variables in the program.

•Three things are mentioned in loop invariants

•1. Initialization

–Prior to the first iteration, i=floor(n/2)

•2. Maintenance

–Variation in the value of i

•3. Termination

–At termination i=0

Analysis of Algorithms Heap Sort

Analysis of Algorithms Heap Sort

•The (binary) heap data structure is an array object that is nearly complete binary tree

•Each node of the tree corresponds to an element of the array that stores the value in the node.

•The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.

•An array A that represents a heap is an object with two attributes:

–length[A], which is the number of elements in the array,

–heap-size[A], the number of elements in the heap stored within array A.

•Given the index of a node, its parent and children can be calculated as

•PARENT(i)

  return ⌊i/2⌋

•LEFT(i)

  return 2i

•RIGHT(i)

  return 2i + 1

•the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf

•The height of the heap to be the height of its root.

•Since a heap of n elements is based on a complete binary tree, its height is Θ(lg n)

Max-Heap Property: For all nodes i, excluding the root. A[Parent(i)] ≥ A[i].

Min-Heap Property: For all nodes i, excluding the root. A[Parent(i)] ≤ A[i].

Example: Max-Heap

 Maintaining the Heap Property

MAX-HEAPIFY(A, i)

   l ← LEFT(i)

   r ← RIGHT(i)

   if l ≤ heap-size[A] and A[l] > A[i]

     then largest ← l

   else largest ← i

   if r ≤ heap-size[A] and A[r] > A[largest]

  then largest ← r

    if largest ≠ i

     then    exchange A[i] ↔ A[largest]

      MAX-HEAPIFY(A, largest)

The way MAX-HEAPIFY works:

•   Compare A[i] , LEFT[i] and RIGHT[i].

•   If necessary, swap A[i] with the larger of the two children to preserve heap property.

•   Continue this process of comparing and swapping down the heap, until subtree rooted at i is max-heap. If we hit a leaf, then the subtree rooted at the leaf is trivially a max-heap.

Run MAX-HEAPIFY on the following heap example

MAX-HEAPIFY

Analysis

Time

O(lg n).

Analysis

Heap is almost-complete binary tree, hence must process O(lg n) levels, with constant work at each level (comparing 3 items and maybe swapping 2).

-Another time is o(h)

-This time is for a node of height ‘h’

Building a Heap

The following procedure, given an unordered array, will produce a max-heap.

BUILD-MAX-HEAP(A)

Heap-size[A] ß length[A]

for i ß Floor(length[A]/2) downto 1

  do MAX-HEAPIFY(A,i)