Question? Leave a message!




d-ary heaps

d-ary heaps
ECE 250 Algorithms and Data Structures dary heaps Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.daryheaps 2 Outline In this topic, we will: – Definition of a dary min heap – Implementation as a complete tree – Examples of binary, ternary, quaternary, and quinary min heaps – Properties – Relative speeds • Optimal choice is a quaternary heapdaryheaps 3 Definition The relationship between a binary min heap and a dary min heap is the same as a binary tree and an Nary tree – Every node has up to d children The relationship is the same—all children are greater than their parentdaryheaps 4 dary heaps as complete Nary trees The implementation of a dary heap is similar to that of a binary heap: use a complete Nary tree which can be stored as an array Observation: – With binary heaps, we started at index 1, and for the entry at index k: • The parent is at k/2 • The children are at 2k and 2k + 1 – Recall the form: parent = k 1; leftchild = k 1; rightchild = leftchild 1;daryheaps 5 dary heaps as complete Nary trees Initial Calculations Operations index parent = (k 2) 2; 3 arithmetic thirdchild = k 2; 3 logic 1 firstchild = thirdchild 2; secondchild = thirdchild 1; fourthchild = thirdchild 1; parent = (k 1) 2; 2 arithmetic firstchild = k 2; 5 logic secondchild = firstchild 2; 0 thirdchild = firstchild 3; fourthchild = firstchild + 4; firstchild = 1; parent = (k 4) 1; 2 arithmetic firstchild = (k + 1) 2; 5 logic 1 secondchild = firstchild 1; thirdchild = firstchild 2; fourthchild = firstchild 3;daryheaps 6 dary heaps as complete Nary trees Finally, if we start at 1, our calculations are: parent = (k 4 1 : k 4; firstchild = (k + 1) 2; secondchild = firstchild 1; thirdchild = firstchild 1; fourthchild = firstchild 1; Now, if we start at index 0, our calculations are: parent = (k 1) 2; firstchild = k 2; secondchild = firstchild 2; thirdchild = firstchild 3; fourthchild = firstchild + 4; firstchild = 1;daryheaps 7 dary heaps as complete Nary trees The implementation of a dary heap is similar to that of a binary heap: we use a complete Nary tree which can be stored as an array To find the root, children, and parent: – The root is at 0 (not 1 like a binary heap) – The children of k are at: dk + 1, dk + 2, ..., dk + d k1 – The parent of k is at for k 0 ddaryheaps 8 Examples Example of a binary minheap: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 5 4 16 7 9 11 15 31 27 12 26 35 23 14 18 17 42daryheaps 9 Examples The same 18 elements in a ternary minheap: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 11 4 5 12 17 14 18 31 27 7 9 35 23 16 15 26 42daryheaps 10 Examples In a quaternary minheap: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 16 4 7 12 26 14 18 31 27 5 9 35 23 11 15 17 42daryheaps 11 Examples And a quinary heap: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 5 4 7 12 26 16 18 31 27 14 9 35 23 11 15 17 42daryheaps 12 Properties The properties of a complete dary heap are: – The average depth of a node is given by the formula 1 h d1 – The proportion of leaf nodes to the full number of nodes is approximately d1 ddaryheaps 13 Properties For example, in a complete quaternary heap: – The average height of a node is h–⅓, and – The leaf nodes comprise ¾ of all nodes Therefore: – A push will require approximately 1⅓ comparisons and ⅓ copies k1  3 1 4  k   k1 4 4 3  – A pop will require almost 4h comparisons (= (3 + 1)h) and h + 1 copiesdaryheaps 14 Relative Speed In general, dary heaps have different performance versus binary heaps: – A dary heap makes log (n) comparisons for each push (worst case) d • Percolating up compares only the parent – A dary heap must, however, make d log (n) comparisons for each pop d • Percolating down compares a node with all d children Assuming an equal number of pushes and pops: log (n) + d log (n) = (d + 1) log (n) d d ddaryheaps 15 Relative Speed Calculating the relative number of comparisons with a binary heap log n  2 d1  d1 log n log d  d1 d 2  3log n 3log n 3log d  2 2 2 83 d – The comparisons are minimized when d = 4:daryheaps 16 Relative Speed A quaternary heap requires 41 5 5  3log 4 3 2 6  2 of the comparisons required for a binary heap – It should be 16.67 fasterdaryheaps 17 Relative Speed From binary heaps, however, a push was Q(1) on average – At least half the entries are stored in leaf nodes Assuming an equal number of pushes and pops, we expect a run time of d log (n) d dn log  d d  Thus, 2lognd 2log  22 This suggests using a ternary 94 heap—not a quaternary heap ddaryheaps 18 Relative Speed In order to test this, 1.5 billion pushes and pops were performed on similar implementations of binary, ternary, quaternary, and quinary min heaps with two cases http://ece.uwaterloo.ca/dwharder/aads/Algorithms/daryheaps/daryheaps 19 Relative Speed Using the worstcase insertions: every newly inserted entry has higher priority than all other entries in the heap: – The time closely follows the pattern we expect – Percent relative to a binary heap d1 Expected time 3log d  2 Actual timedaryheaps 20 Relative Speed However, if we make random insertions, we get closer to the other expected pattern—a ternary tree appears to be better – Percent relative to a binary heap d Expected time 2log d  2 Actual timedaryheaps 21 Cache Why are the runtimes better than expected – Recall that the cache is faster than main memory: Cache 1 GHz Main memory (SDRAM): 100 MHz – Recall that the cache is faster than main memory but not every page can be cached simultaneously • Fewer memory accesses may result in fewer cache missesdaryheaps 22 Summary In this topic, we: – Defined dary min heaps • nary trees interpreted as heaps – Similar array implementation for complete dary heaps – Saw some examples – Properties of the complete heaps – Ternary heaps are apparently optimal • Actual tests partially confirms the theoretical limitsdaryheaps 23 References 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, §7.13, p.152. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §6.56, p.21525.daryheaps 24 Usage Notes • These slides are made publicly available on the web for anyone to use • If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: – that you inform me that you are using the slides, – that you acknowledge my work, and – that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath dwharderalumni.uwaterloo.ca
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017