are two main types of heaps:

**HEAPS**

**A PROGRAMMING DATA STRUCTURE**

Why use a Heap?

A heap can be thought of as a priority queue ; the most important node will always be at the top, and when removed, its replacement will be the most important

The Operations of Heaps

While heaps in theory may seem very simple, being able to implement it is a bit more challenging

"Upheaping"

Remember the node being upheaped is greater than its parent, and its parent is greater than its own parent, all the way up to the root.

So How does a Heap

physically sort?

A White Board Example

**The Types of Heaps**

1) The Minimum Heap (Min Heap)

So. . . what is a heap?

It is a way of organizing data into a specific structure or form, one that resembles the shape of a tree with many branches and its individual leaves

"Downheaping"

This type of heap is organized similar to a tree with branches where the numbers range from small to big from the top of the tree to the bottom of the tree

2) The Maximum Heap (Max Heap)

Just like a Min Heap, a max heap organizes the numbers in reverse (big to small)

Presented By:

Alexander DeSouza

Kashish Verma

Ipsita H. Bhargava

What is a heap?

A Java Example

Interactive Activity

A heap is a data structure in the shape of a tree

At first glance, a heap may not look completely organized but in reality is sorted due to a particular sorting algorithm

When drawn out, heaps look like a tree, with each leaf given the term "Node", branching out to form ``Children``

Depending on the types of heaps (discussed later) the values in the nodes either get bigger or smaller from top to bottom

Heaps are also considered to be complete trees, thus being no gaps between any of the leaves (The left child always is referenced first)

This can be useful when coding algorithms that require certain things to be in complete order but do not need a full sort of need to know information about all the nodes within the tree

Heaps is also the basis for successfully performing a sorting method known as the "heap sort"

Big O

The Speed of A Heap Sort

There are two processes for handling the addition and subtraction of nodes within heaps

These are respectively called "Upheap" and "Downheap"

The first operation is adding nodes to the heap (Upheaping)

This works by comparing your current node value the one just added) to its parent node value (ie: assume int's/#'s are compared)

Nodes are always added to the bottom most left hand corner of a heap

When added, the first operation that must be undertaken is to upheap the node, to keep the heap partially sorted from bottom to top (big to small)

However, if the condition is met (Parent node value is less than the child node) the process can be stopped all together

Ipsita H. Bhargava

When a node is to be removed from the heap, the process is known as "Downheaping"

To begin the process, you compare the parent node to both or one of its children

If the node is less than its children, it remains in place

However, if the node it greater than one or both of it's children, then you swap the child containing the lowest number

Thus the new parent node contains the lowest value and ensures that all three nodes (One parent, and two childs) have been compared

Remember that "downheaping" process does not ensure that all the odes are in proper position, meaning this process must be repeated until the node is less than both of its children

The Efficiency of Heaps

To measure the efficiency of heaps, we will assume that the heap has "N" nodes

The efficiency of heaps can truly be measured through both methods of Inserting Nodes and Removing Nodes

EFFICIENCY OF INSERTING

Since the insert swaps at the maximum once per level, the highest complexity of the insert would result in O(log N)

EFFICIENCY OF REMOVING

Again, since the remove swaps at maximum once per level, the order of complexity of removing is also O(log N)

Presented By:

Presented By:

Kashish Verma

Great! But How Is This Useful to us Programmers?

**A Java Demo.**

(Using Heap Sorts)

http://www.cprogramming.com/tutorial/computersciencetheory/heap.html

Resource References

**Thank You For Watching.**

Most often, the maximum number of "children" a parent can have is Two. This is known as a binary heap

http://en.wikipedia.org/wiki/Heap_(data_structure)

**Variations of the Heap**

Besides the two main types of Heaps, there are many other types of "Heaps" out there in the programming world

Below are just a sample of some of the variants of heaps, each with it's own structure and rules:

2-3 Heap

Binary Heap

Binomial Heap

d-ary Heap

Leftist Heap

Pairing Heap

Skew Heap

Soft Heap

Weak Heap

Radix Heap

Leaf Heap

Best & Worst Cases

of Heaps

Best Case:

Worst Case:

The best case for heaps is if all the data found within the nodes are in order or if there are duplicate numbers, then Heap sort will not be needed

The worst case for heaps is for the numbers to be all out of order

Visualizing

HEAP SORT

Through Sound.

Deck of Cards Example:

Highest

Lowest

Lowest

The Functions of Heaps

Books and Textbook Resources

"Introduction to Algorithms" - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Website & Internet Resources

Video & Media Resources

Highest

Presented By:

Alexander DeSouza

Similarities

Both data structures are in the shape of a tree, with branches and leaves known as "Nodes"

Differences

Both data structures are sorted differently and read differently

Similarities & Difference to BST vs. Heaps

Interactive Activity/Game

"The 4 Min Challenge"

Not a Pile of Clothes.

What We Will Use:

Both data structures are efficient and extensible when used with a linked data structure

Most heaps are complete binary trees, nodes must exist always from the most left tail in the tree (ie: no gaps)

AVG CASE:

This makes Heap Sort extremely efficient when dealing with large amounts of data

(nLog n)

Example- 10 #'s = 1 sec,

100 #'s = 2 secs

Logarithmic Graph

Advantages & Disadvantages

of Using Heaps:

Advantages:

Reasonable fast in worst and average cases, n lg n + O(n)+ in place- best case still n log n

Low memory usage, "Heap Sort" doesn't require a lot of extra memory space to sort data

Disadvantages:

"Sorting Algorithms in 6 mins" - Online Youtube Video

"Heap Sort" - Online Youtube Video

UMLs of Java Demo

By using a heap as a linked list, none of the operations will be worse than O log n.

O(n log n)

O(n log n)