Skip to content

Latest commit

 

History

History
42 lines (37 loc) · 2.73 KB

20150120.md

File metadata and controls

42 lines (37 loc) · 2.73 KB
Raw

CS 240 Enriched

Data Structures and Data Management

1/20/2015

Elvin Yung

Heap

  • A max-heap is a binary tree that has the following properties:

    • The heap property: the priotiy of the parent is always higher than the priority of the child.
    • Structural property: It's a complete tree, with at most one node of degree one.
    • The leaves at most one level apart
    • The bottom level is filled from left to right (left-justified)

  • A min-heap is the same, but with opposite order property.

  • Theorem: The height of a heap with n nodes is Ө(log n).

    • Proof: (basic Ө proof with $1+...+2^n < n < 1+...+2^{n+1}$)

  • To insert a new node to a heap, we perform the bubble-up technique:

    • Insert the new node at the bottom bottom level, at the leftmost free spot.
    • Compare the node's value with its parent. If it is breaking heap property, switch them.
    • Continue until the heap property is no longer broken.

  • To delete the maximum value from the heap:

    • Remove the root.
    • Promote the largest of the root's two children.
    • Continue until done.

  • We can represent a heap (or any binary tree in general) with an array where the children of some node at index i are respectively at 2i+1 and 2i+2. The parent of i must then be at floor((i-1)/2).

  • Representing the heap with an array is an example of an implicit data structure. Implicit data structures are very efficient spacewise because they store very little information other than the data itself, and meaning is instead carried in the arrangement of the data.

  • Now we can implement a priority queue using a heap, by inserting each item as a key of variable priorities, and then using deleteMax to dequeue. Now both operations run at $\theta(n log n)$.

heapify

  • heapify is an operation which creates a heap from some collection of data in worst case Ө(n) using a bottom-up construction method.
  • Essentially, starting from the smallest subtrees (at the bottom), check and swap for heap order. Do the same until root is reached.
  • The alternative implementation is from top-down, which is Ө(n log n) in the worst case, and Ө(n) on average case.
  • From the root, check and promote children, until heap property is no longer violated.

Heap Sort

  • Heap sort essentially works by heapifying some collection A, and then running deleteMax until the heap is empty.
  • The running time of heap sort is roughly O(n log n).

Treaps

  • The term treap was coined from combining the terms tree and heap. Tricky.
  • A treap is simultaneously a heap and a binary search tree.
  • Suppose we have some collection X in which each item has a key and a priority.
  • The key follows binary search property, but the priority follows the heap property.