1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!-- Created with Inkscape (http://www.inkscape.org/) --> 3<svg 4 xmlns:dc="http://purl.org/dc/elements/1.1/" 5 xmlns:cc="http://web.resource.org/cc/" 6 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 7 xmlns:svg="http://www.w3.org/2000/svg" 8 xmlns="http://www.w3.org/2000/svg" 9 xmlns:xlink="http://www.w3.org/1999/xlink" 10 xmlns:sodipodi="http://inkscape.sourceforge.net/DTD/sodipodi-0.dtd" 11 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 12 width="11in" 13 height="8.5in" 14 id="svg2" 15 sodipodi:version="0.32" 16 inkscape:version="0.43" 17 version="1.0" 18 sodipodi:docbase="/mnt/share/src/policy_based_data_structures/pb_ds_images" 19 sodipodi:docname="pq_tag_diagram_2.svg" 20 inkscape:export-filename="/mnt/share/src/policy_based_data_structures/pb_ds_images/pq_tag_diagram_2.png" 21 inkscape:export-xdpi="90" 22 inkscape:export-ydpi="90"> 23 <defs 24 id="defs4"> 25 <marker 26 inkscape:stockid="Arrow1Mstart" 27 orient="auto" 28 refY="0.0" 29 refX="0.0" 30 id="Arrow1Mstart" 31 style="overflow:visible"> 32 <path 33 id="path3311" 34 d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " 35 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none" 36 transform="scale(0.4)" /> 37 </marker> 38 <marker 39 inkscape:stockid="Arrow2Sstart" 40 orient="auto" 41 refY="0" 42 refX="0" 43 id="Arrow2Sstart" 44 style="overflow:visible"> 45 <path 46 id="path3319" 47 style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" 48 d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.97309,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " 49 transform="matrix(0.3,0,0,0.3,-1.5,0)" /> 50 </marker> 51 <marker 52 inkscape:stockid="Arrow1Sstart" 53 orient="auto" 54 refY="0" 55 refX="0" 56 id="Arrow1Sstart" 57 style="overflow:visible"> 58 <path 59 id="path3337" 60 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z " 61 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none" 62 transform="scale(0.2,0.2)" /> 63 </marker> 64 <marker 65 inkscape:stockid="Arrow2Send" 66 orient="auto" 67 refY="0" 68 refX="0" 69 id="Arrow2Send" 70 style="overflow:visible"> 71 <path 72 id="path3316" 73 style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" 74 d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.97309,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " 75 transform="matrix(-0.3,0,0,-0.3,1.5,0)" /> 76 </marker> 77 <marker 78 inkscape:stockid="Arrow2Mend" 79 orient="auto" 80 refY="0" 81 refX="0" 82 id="Arrow2Mend" 83 style="overflow:visible"> 84 <path 85 id="path3322" 86 style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" 87 d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.97309,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " 88 transform="matrix(-0.6,0,0,-0.6,3,0)" /> 89 </marker> 90 <marker 91 inkscape:stockid="Arrow1Lend" 92 orient="auto" 93 refY="0" 94 refX="0" 95 id="Arrow1Lend" 96 style="overflow:visible"> 97 <path 98 id="path3346" 99 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z " 100 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none" 101 transform="scale(-0.8,-0.8)" /> 102 </marker> 103 <marker 104 inkscape:stockid="Arrow2Lstart" 105 orient="auto" 106 refY="0" 107 refX="0" 108 id="Arrow2Lstart" 109 style="overflow:visible"> 110 <path 111 id="path3331" 112 style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" 113 d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.97309,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " 114 transform="matrix(1.1,0,0,1.1,-5.5,0)" /> 115 </marker> 116 <marker 117 inkscape:stockid="Arrow2Lend" 118 orient="auto" 119 refY="0" 120 refX="0" 121 id="Arrow2Lend" 122 style="overflow:visible"> 123 <path 124 id="path3328" 125 style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" 126 d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.97309,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " 127 transform="matrix(-1.1,0,0,-1.1,5.5,0)" /> 128 </marker> 129 </defs> 130 <sodipodi:namedview 131 id="base" 132 pagecolor="#ffffff" 133 bordercolor="#666666" 134 borderopacity="1.0" 135 inkscape:pageopacity="0.0" 136 inkscape:pageshadow="2" 137 inkscape:zoom="2" 138 inkscape:cx="608.69002" 139 inkscape:cy="490.05621" 140 inkscape:document-units="in" 141 inkscape:current-layer="layer1" 142 showguides="true" 143 inkscape:guide-bbox="true" 144 inkscape:window-width="1278" 145 inkscape:window-height="973" 146 inkscape:window-x="0" 147 inkscape:window-y="0" 148 gridtolerance="0.125in" 149 guidetolerance="0.125in"> 150 <sodipodi:guide 151 orientation="horizontal" 152 position="629" 153 id="guide1307" /> 154 <sodipodi:guide 155 orientation="horizontal" 156 position="449" 157 id="guide1309" /> 158 <sodipodi:guide 159 orientation="horizontal" 160 position="269" 161 id="guide1311" /> 162 <sodipodi:guide 163 orientation="vertical" 164 position="496" 165 id="guide1313" /> 166 <sodipodi:guide 167 orientation="vertical" 168 position="383" 169 id="guide1315" /> 170 <sodipodi:guide 171 orientation="vertical" 172 position="241" 173 id="guide1317" /> 174 <sodipodi:guide 175 orientation="vertical" 176 position="680" 177 id="guide1319" /> 178 <sodipodi:guide 179 orientation="vertical" 180 position="749" 181 id="guide1321" /> 182 <sodipodi:guide 183 orientation="vertical" 184 position="124" 185 id="guide1345" /> 186 <sodipodi:guide 187 orientation="vertical" 188 position="901" 189 id="guide1347" /> 190 <sodipodi:guide 191 orientation="horizontal" 192 position="539" 193 id="guide3390" /> 194 <sodipodi:guide 195 orientation="horizontal" 196 position="359" 197 id="guide3392" /> 198 <sodipodi:guide 199 orientation="vertical" 200 position="280.5" 201 id="guide3324" /> 202 <sodipodi:guide 203 orientation="vertical" 204 position="195" 205 id="guide3326" /> 206 <sodipodi:guide 207 orientation="vertical" 208 position="427" 209 id="guide3328" /> 210 <sodipodi:guide 211 orientation="vertical" 212 position="795" 213 id="guide3340" /> 214 <sodipodi:guide 215 orientation="horizontal" 216 position="179" 217 id="guide1395" /> 218 </sodipodi:namedview> 219 <metadata 220 id="metadata7"> 221 <rdf:RDF> 222 <cc:Work 223 rdf:about=""> 224 <dc:format>image/svg+xml</dc:format> 225 <dc:type 226 rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> 227 <dc:creator> 228 <cc:Agent> 229 <dc:title>Benjamin Kosnik</dc:title> 230 </cc:Agent> 231 </dc:creator> 232 </cc:Work> 233 </rdf:RDF> 234 </metadata> 235 <g 236 inkscape:label="Layer 1" 237 inkscape:groupmode="layer" 238 id="layer1"> 239 <rect 240 y="382.17499" 241 x="241.73018" 242 height="23.200001" 243 width="141.64481" 244 id="rect3420" 245 style="fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:1.25;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" /> 246 <rect 247 style="fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:1.25;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" 248 id="rect3418" 249 width="141.64481" 250 height="23.200001" 251 x="52.730194" 252 y="382.17499" /> 253 <text 254 xml:space="preserve" 255 style="font-size:9.60000038;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:100%;writing-mode:lr;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 256 x="122.35258" 257 y="395.91092" 258 id="text3394" 259 sodipodi:linespacing="100%"><tspan 260 sodipodi:role="line" 261 id="tspan1383" 262 x="122.35258" 263 y="395.91092">pairing_heap_tag</tspan></text> 264 <text 265 sodipodi:linespacing="100%" 266 id="text3400" 267 y="395.91092" 268 x="310.55255" 269 style="font-size:9.60000038;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:100%;writing-mode:lr;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 270 xml:space="preserve"><tspan 271 sodipodi:role="line" 272 id="tspan1381" 273 x="310.55255" 274 y="395.91092">bionomial_heap_tag</tspan></text> 275 <rect 276 style="fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:1.25;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" 277 id="rect3380" 278 width="141.64481" 279 height="23.200001" 280 x="425.57764" 281 y="292.56177" /> 282 <text 283 xml:space="preserve" 284 style="font-size:9.60000038;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:100%;writing-mode:lr;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1.5625;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans" 285 x="495.20001" 286 y="307.09772" 287 id="text1323" 288 sodipodi:linespacing="100%"><tspan 289 sodipodi:role="line" 290 id="tspan1363" 291 x="495.20001" 292 y="307.09772">priority_queue_tag</tspan></text> 293 <path 294 style="fill:none;fill-opacity:0.75;fill-rule:evenodd;stroke:#000000;stroke-width:1.16226137;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" 295 d="M 124.54034,382.1132 L 124.54034,360.6132 L 311.75594,359.6132 L 311.75594,382.1132" 296 id="path2244" /> 297 <rect 298 style="fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:1.25;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" 299 id="rect3422" 300 width="141.64481" 301 height="23.200001" 302 x="425.73022" 303 y="382.17499" /> 304 <text 305 sodipodi:linespacing="100%" 306 id="text3406" 307 y="395.91092" 308 x="495.3526" 309 style="font-size:9.60000038;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:100%;writing-mode:lr;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans" 310 xml:space="preserve"><tspan 311 sodipodi:role="line" 312 id="tspan1377" 313 x="495.3526" 314 y="395.91092">rc_binomial_heap_tag</tspan></text> 315 <rect 316 y="382.17499" 317 x="607.93024" 318 height="23.200001" 319 width="141.64481" 320 id="rect3424" 321 style="fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:1.25;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" /> 322 <text 323 xml:space="preserve" 324 style="font-size:9.60000038;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:100%;writing-mode:lr;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans" 325 x="679.15259" 326 y="395.91092" 327 id="text3412" 328 sodipodi:linespacing="100%"><tspan 329 sodipodi:role="line" 330 id="tspan1379" 331 x="679.15259" 332 y="395.91092">binary_heap_tag</tspan></text> 333 <path 334 id="path3347" 335 d="M 495.79886,382.13056 L 495.79886,321.40547" 336 style="fill:none;fill-opacity:0.75;fill-rule:evenodd;stroke:#000000;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" /> 337 <rect 338 style="fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:1.25;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" 339 id="rect2281" 340 width="141.64481" 341 height="23.200001" 342 x="795.625" 343 y="382.17499" /> 344 <text 345 sodipodi:linespacing="100%" 346 id="text2283" 347 y="395.91092" 348 x="866.84735" 349 style="font-size:9.60000038;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:100%;writing-mode:lr;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans" 350 xml:space="preserve"><tspan 351 sodipodi:role="line" 352 id="tspan1359" 353 x="866.84735" 354 y="395.91092">thin_heap_tag</tspan></text> 355 <path 356 style="fill:none;fill-opacity:0.75;fill-rule:evenodd;stroke:#000000;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" 357 d="M 311.5,360 L 680,360" 358 id="path2309" /> 359 <use 360 x="0" 361 y="0" 362 xlink:href="#path2244" 363 id="use2311" 364 transform="matrix(-1,0,0,1,992.3371,0)" 365 width="990" 366 height="765" /> 367 </g> 368</svg> 369