Interval HeapsIntervalExample Interval HeapSlide 4Insert An ElementAnother InsertSlide 7Slide 8Yet Another InsertAfter 82 InsertedOne More Insert ExampleAfter 8 Is InsertedRemove Min ElementRemove Min Element ExampleSlide 15Slide 16Slide 17Slide 18InitializeCache OptimizationCache Aligned Arrayd-ary Heapd = 4, 4-Heap4-Heap Cache Utilizationd-ary Heap PerformanceApplication Of Interval HeapsExampleSlide 28Interval Heaps•Complete binary tree.•Each node (except possibly last one) has 2 elements.•Last node has 1 or 2 elements.•Let a and b be the elements in a node P, a <= b.•[a, b] is the interval represented by P.•The interval represented by a node that has just one element a is [a, a].•The interval [c, d] is contained in interval [a, b] iff a <= c <= d <= b.•In an interval heap each node’s (except for root) interval is contained in that of its parent.Interval•[c,d] is contained in [a,b]•a <= c•d <= ba bc dExample Interval Heap28,55 3525,60 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,7015,8030,6010,90Left end points define a min heap.Right end points define a max heap.28,55 3525,60 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,7015,8030,6010,90Min and max elements are in the root.Store as an array.Height is ~log2 n.Example Interval HeapInsert An Element28,55 3525,60 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,7015,8030,6010,90Insert 27.3527,35New element becomes a left end point.Insert new element into min heap.Another Insert28,55 3525,60 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,7015,8030,6010,90Insert 18.35New element becomes a left end point.Insert new element into min heap.28,55 25,3525,60 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,7015,8030,6010,90Insert 18. ,60New element becomes a left end point.Insert new element into min heap.Another Insert28,55 25,3520,60 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,7015,8030,6010,90Insert 18. ,70New element becomes a left end point.Insert new element into min heap.18,70Another InsertYet Another Insert28,55 3525,60 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,7015,8030,6010,90Insert 82.35New element becomes a right end point.Insert new element into max heap.After 82 Inserted28,55 35,6025,70 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,8015,8230,6010,9028,5525,70 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,8015,8230,6010,90One More Insert ExampleInsert 8.New element becomes both a left and a right end point.Insert new element into min heap.2528,5520,70 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2015,8010,8230,60 8,90After 8 Is InsertedRemove Min Element•n = 0 => fail.•n = 1 => heap becomes empty.•n = 2 => only one node, take out left end point.•n > 2 => not as simple.Remove Min Element Example28,55 35,6025,70 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,8015,8230,6010,90Remove left end point from root.Remove left end point from last node.Reinsert into min heap, begin at root. ,90 ,60Delete last node if now empty.3528,55 6025,70 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,8015,8230,6015,90Swap with right end point if necessary. ,8235Remove Min Element Example28,55 6025,70 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,8015,8230,6015,90Swap with right end point if necessary. ,2035Remove Min Element Example28,55 6025,70 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6016,3520,8015,8230,6015,90Swap with right end point if necessary. ,1920Remove Min Element Example28,55 6025,70 30,50 19,20 17,17 50,55 47,58 40,45 40,4335,5045,6016,3520,8015,8230,6015,90Remove Min Element ExampleInitialize68,55 35,1425,19 57,50 46,19 17,37 50,25 47,28 20,45 40,1335,5049,6348,2020,2399,821,1270,39Examine nodes bottom to top.Swap end points in current root if needed.Reinsert right end point into max heap.Reinsert left end point into min heap.Cache Optimization•Heap operations.Uniformly distributed keys.Insert percolates 1.6 levels up the heap on average.Remove min (max) height – 1 levels down the heap.•Optimize cache utilization for remove min (max).Cache Aligned Array•L1 cache line is 32 bytes.•L1 cache is 16KB.•Heap node size is 8 bytes (1 8-byte element). •4 nodes/cache line.0 1 2 3 4 5 6 70 1 2 3 4 5 6 7•A remove min (max) has ~h L1 cache misses on average.Root and its children are in the same cache line.~log2n cache misses.Only half of each cache line is used (except root’s).d-ary Heap•Complete n node tree whose degree is d.•Min (max) tree.•Number nodes in breadth-first manner with root being numbered 1.•Parent(i) = ceil((i – 1)/d).•Children are d*(i – 1) + 2, …, min{d*i + 1, n}.•Height is logdn.•Height of 4-ary heap is half that of 2-ary heap.d = 4, 4-Heap•Worst-case insert moves up half as many levels as when d = 2.Average remains at about 1.6 levels.•Remove-min operations now do 4 compares per level rather than 2 (determine smallest child and see if this child is smaller than element being relocated).But, number of levels is half.Other operations associated with remove min are halved (move small element up, loop iterations, etc.)4-Heap Cache Utilization•Standard mapping into cache-aligned array.0 1 2 3 4 5 6 7- - - 1 2 3 4 50 1 2 3 4 5 6 70 1 2 3 4 5 6 7•Siblings are in 2 cache lines.~log2n cache misses for average remove min (max).•Shift 4-heap by 2 slots.•Siblings are in same cache line.~log4n cache misses for average remove min (max).d-ary Heap Performance•Speedup of about 1.5 to 1.8 when sorting 1 million elements using heapsort and cache-aligned 4-heap vs. 2-heap that begins at array position 0.•Cache-aligned 4-heap generally performs as well as, or better, than other d-heaps.•Use degree 4 complete tree for interval heaps instead of degree 2.Application Of Interval Heaps•Complementary range search problem.Collection of 1D points (numbers).Insert a point.•O(log n)Remove a point given its location in the structure.•O(log n)Report all points not in the range [a,b], a <= b.•O(k), where k is the number of points not in the range.Example28,55 3525,60 30,50 16,19 17,17 50,55 47,58 40,45 40,4335,5045,6015,2020,7015,8030,6010,90[5,100][2,65]Example28,55 3525,60 30,50 16,19 17,17 50,55 47,58 40,45