Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Heaps: A Data Structure
Transcript of Heaps: A Data Structure
are two main types of 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
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
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
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)
Ipsita H. Bhargava
What is a heap?
A Java Example
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"
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)
Great! But How Is This Useful to us Programmers?
A Java Demo.
(Using Heap Sorts)
Thank You For Watching.
Most often, the maximum number of "children" a parent can have is Two. This is known as a binary heap
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:
Best & Worst Cases
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
Deck of Cards Example:
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
Both data structures are in the shape of a tree, with branches and leaves known as "Nodes"
Both data structures are sorted differently and read differently
Similarities & Difference to BST vs. Heaps
"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)
This makes Heap Sort extremely efficient when dealing with large amounts of data
Example- 10 #'s = 1 sec,
100 #'s = 2 secs
Advantages & Disadvantages
of Using Heaps:
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
"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)