Das wichtigste natürlich wie immer zuerst: Die Kopfkoordinaten sind natürlich rein fiktiv, hier kann man keinen Cache finden.
Langsam entbrennt ein regelrechter Wettlauf unter den Cachern des Brecher Organisationsteams. Wer sortiert die PETlinge am effektivsten? Die eigentliche Mission ein schönes Event zu gestalten ist schon völlig vergessen gegangen, es geht nur noch um Ordnung. „Ordnung kann man auch im Haufen haben!“ ruft plötzlich einer der Teammitglieder. Seine Lieblingsschrotthändler aus dem Westerwald – die Ludolf Brüder – würden es ganz genauso machen. Die werfen alles auf einen Haufen und haben trotzdem Ordnung in der Bude. Da muss man doch auch etwas draus machen können? In der Tat! Das weite Feld der Informatik stellt uns hier nämlich ein sehr interessantes Konstrukt bereit, dass sogar den Namen „Haufen“ trägt :-)
Ich zeige euch mal einen solchen Haufen.
Diese Haufen – im Englischen auch Heap genannt – werden auch als (vollständige) binäre Bäume bezeichnet. Ganz oben steht die Wurzel, ganz unten die Blätter. Dazwischen befinden sich weitere Knoten. Dieser Heap hat eine ganz besondere Eigenschaft: Das größte Element muss immer in der Wurzel stehen. Diesen Heap kann man auch ganz einfach in eine Liste übertragen:
Auch diese Darstellung hat wieder eine Besonderheit: Sucht man z.B. den linken Kindsknoten der Zahl 6, muss man nur deren Index i*2 = 3*2 rechnen, und schon hat man den linken Kindsknoten mit dem Index 6. Sucht man das rechte Kind, muss man den Index i*2 + 1 = 3*2 + 1 rechnen. Sucht man den Elternknoten der 6, teilt man deren Index durch 2 und rundet auf die nächste ganze Zahl ab, kommt also auf den Index 1 und damit die Zahl 7. Die Wurzel und damit die größte Zahl ist immer das erste Element in der Liste mit dem Index 1. Eine weitere Eigenschaft, die man sich merken kann ist die heap_size, also die Anzahl der Knoten im Heap. Hier wäre heap_size = 7. Alles in allem eine schöne Sache :-)
Die besondere Eigenschaft, dass das größte Element immer im Elternknoten, bzw. der Wurzel steht, wird als Heap-Eigenschaft bezeichnet. Die Kinderknoten müssen also immer kleinere Zahlen beinhalten, als der Elternknoten. Der oben abgebildete Heap erfüllt diese Bedingung für alle Knoten. Man könnte jetzt also den Knoten mit der 7 in der Wurzel wegnehmen und sagen, dass man in ihm das größte Element gefunden hat. Nun ersetzt man diesen Knoten einfach mit demjenigen Knoten, der am Ende des Heaps steht (d.h. so weit wie möglich unten und so weit wie möglich rechts). In diesem Fall Knoten 7 mit der Zahl 1:
Das blöde ist jetzt: Die Heap-Eigenschaft ist nicht mehr erfüllt, weil 1 ja nicht die größte Zahl ist! Es muss also ein Verfahren her, dass dieses Problem löst. Man nennt es oft heapify und es funktioniert folgendermaßen (hier im Beispiel wird heapify für den Knoten 1 ausgeführt):
- Man betrachtet den Knoten und seine 2 Kinder und sucht den Knoten mit dem größten Element. Dafür sollte auch überprüft werden, ob der Index des linken und rechten Kinds kleiner oder gleich der heap_size ist. Damit verhindert man, dass Knoten gesucht werden, die nicht existieren (z.B. den Kindknoten mit Index 7).
- Ist das größte Element nicht der Elternknoten, dann vertausche den Elternknoten mit dem größten der beiden Kindsknoten.
- Führe die heapify-Funktion für den Kindsknoten aus, der grade getauscht wurde.
Auf diese Art und Weise versickert der Knoten mit der kleinen Zahl immer weiter nach unten, bis er seine richtige Position erreicht hat. In unserem Beispiel würde die 1 mit der 6 getauscht. Anschließend nochmal die 1 mit 4:
Nun steht die 6 in der Wurzel. Sie kann als nächste größte Zahl entfernt werden und das Spiel beginnt erneut. Dieses Verfahren scheint sich also super zum Sortieren zu eignen. Dafür geht man wie folgt vor:
Zu Beginn hat man eine beliebige Zahlenfolge, die höchstwahrscheinlich nicht die Heap-Eigenschaft erfüllt. Man führt die heapify-Funktion einfach erstmal für alle Knoten aus, die keine Blätter sind, weil die Blätter sowieso keine Kinder mehr haben mit denen sie vertauscht werden können. Diese Knoten kann man leicht bestimmen. Es sind alle Knoten, deren Index kleiner oder gleich
ist. Bei unserem Eingangsbeispiel wären es insgesamt 7 Knoten. Geteilt durch 2 und abgerundet auf die nächste ganze Zahl, müsste die heapify-Funktion für alle Knoten mit einem Index kleiner gleich 3 ausgeführt werden (also für die Knoten 3, 2 und 1 in unserem Beispiel). Das stimmt tatsächlich, denn alle Knoten mit einem größeren Index sind Blätter. Nachdem man also diesen ersten großen Schritt gegangen ist, kann man folgendermaßen sortieren: Für alle Knoten im Heap (solange noch mindestens 2 Knoten vorhanden sind) werden die folgenden Anweisungen ausgeführt:
- Vertausche das größte Element in der Wurzel mit dem letzten Element.
- Verringere die heap_size um 1, sodass das aktuell sortierte größte Element außer Acht gelassen wird.
- Führe die heapify-Funktion für den Knoten mit Index 1 aus.
Das war’s! Am Ende sollte man nun ein sortiertes Zahlenfeld erhalten :-)
Dieses Verfahren findet der Statistik-Cacher gar nicht so abwegig. Der Vorteil ist, beim Suchen und Vertauschen von Elementen, muss man nur die Äste des Baumes verfolgen. Bei unserem Baum mit 7 Knoten, müssen von oben bis unten also in jedem Fall maximal 2 Äste besucht werden. „Viel effektiver, als jedes Element mehrmals in die Hand zu nehmen“ denkt sich der Cacher. Er macht sich also gleich ans Werk. Wieder liegen die ganzen Dosen vor ihm:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 822, 450, 624, 122, 144, 247, 976, 803, 242, 438, 340, 250, 270, 374, 383, 605, 590, 571, 367, 330, 993, 319, 585, 865, 926, 197, 673, 727, 574, 168, 572, 743, 1000, 159, 423, 790, 665, 736, 193, 816, 869, 153, 542, 689, 884, 745, 989, 813, 468, 744, 352, 889, 485, 175, 881, 979, 821, 323, 616, 389, 298, 375, 283, 556, 569, 967, 629, 713, 702, 971, 183, 842, 230, 843, 296, 759, 312, 315, 925, 880, 581, 915, 652, 687, 437, 598, 458, 635, 287, 320, 506, 617, 362, 466, 717, 439, 678, 373, 623, 784, 804, 278, 397, 207, 773, 403, 218, 414, 226, 681, 327, 645, 706, 820, 649, 396, 432, 772, 526, 333, 173, 747, 902, 540, 463, 351, 524, 753, 789, 467, 483, 261, 530, 391, 244, 907, 877, 501, 292, 399, 900, 253, 544, 553, 966, 917, 754, 174, 344, 136, 798, 356, 796, 625, 701, 631, 126, 448, 811, 162, 782, 953, 408, 275, 791, 593, 726, 560, 163, 361, 237, 484, 415, 282, 879, 555, 192, 722, 920, 297, 632, 557, 964, 895, 529, 823, 893, 308, 614, 547, 668, 746, 965, 970, 862, 139, 503, 299, 234, 943, 477, 996, 734, 418, 406, 723, 761, 871, 732, 551, 416, 479, 700, 863, 243, 562, 799, 422, 272, 213, 514, 897, 502, 219, 690, 123, 733, 851, 850, 309, 471, 712, 819, 788, 675, 143, 924, 956, 930, 441, 921, 519, 859, 888, 792, 494, 716, 954, 357, 945, 370, 766, 891, 224, 525, 724, 167, 584, 817, 548, 276, 644, 583, 646, 935, 767, 856, 922, 305, 252, 919, 401, 853, 937, 674, 639, 260, 273, 987, 185, 128, 628, 968, 335, 184, 489, 227, 595, 962, 545, 328, 258, 388, 800, 212, 400, 148, 814, 324, 145, 941, 480, 588, 985, 214, 659, 615, 929, 848, 841, 570, 204, 535, 302, 240, 641, 933, 289, 657, 321, 636, 882, 977, 683, 342, 444, 497, 537, 131, 932, 515, 233, 912, 846, 453, 999, 304, 648, 587, 719, 958, 465, 424, 684, 656, 413, 861, 288, 825, 206, 794, 838, 923, 536, 827, 527, 462, 606, 721, 369, 225, 604, 246, 121, 762, 407, 660, 739, 679, 774, 951, 249, 265, 133, 992, 867, 711, 459, 125, 508, 500, 815, 695, 513, 199, 728, 662, 786, 368, 410, 749, 232, 840, 341, 436, 151, 688, 708, 973, 834, 969, 251, 775, 285, 696, 520, 512, 359, 768, 669, 828, 293, 160, 314, 460, 511, 178, 801, 504, 564, 518, 451, 974, 883, 829, 364, 181, 322, 395, 898, 129, 855, 349, 836, 903, 211, 157, 231, 200, 758, 908, 984, 878, 189, 972, 610, 130, 472, 149, 179, 640, 948, 201, 533, 909, 180, 667, 366, 326, 676, 155, 663, 457, 269, 983, 209, 132, 402, 936, 236, 534, 336, 405, 493, 182, 378, 931, 546, 844, 872, 577, 580, 661, 946, 594, 741, 452, 347, 345, 797, 618, 868, 196, 385, 266, 509, 955, 507, 481, 210, 826, 653, 284, 150, 141, 241, 715, 579, 894, 707, 217, 582, 621, 434, 750, 990, 417, 522, 832, 934, 694, 812, 905, 313, 637, 738, 152, 316, 190, 864, 573, 835, 146, 166, 995, 194, 280, 730, 505, 664, 655, 433, 412, 372, 140, 440, 549, 597, 763, 411, 254, 329, 238, 642, 290, 461, 771, 858, 714, 963, 704, 550, 949, 705, 857, 916, 360, 268, 499, 198, 404, 420, 756, 666, 510, 215, 824, 267, 777, 496, 303, 960, 780, 470, 446, 633, 176, 612, 939, 735, 355, 517, 698, 338, 409, 435, 839, 906, 576, 205, 478, 449, 630, 346, 860, 886, 447, 672, 691, 318, 473, 558, 575, 239, 430, 778, 137, 849, 392, 229, 602, 138, 235, 899, 870, 245, 600, 729, 975, 255, 307, 259, 216, 942, 650, 911, 779, 257, 331, 262, 950, 959, 256, 135, 228, 831, 300, 998, 488, 386, 765, 795, 626, 764, 988, 306, 454, 482, 847, 429, 978, 938, 940, 802, 742, 532, 222, 982, 543, 874, 127, 991, 892, 154, 622, 334, 521, 709, 837, 281, 873, 944, 913, 455, 445, 896, 539, 147, 456, 671, 177, 393, 770, 651, 866, 961, 807, 263, 295, 172, 634, 793, 692, 876, 442, 737, 854, 371, 286, 725, 538, 223, 498, 491, 748, 431, 578, 703, 808, 187, 740, 348, 757, 311, 685, 343, 427, 783, 464, 332, 910, 927, 487, 810, 443, 195, 591, 566, 686, 186, 358, 170, 317, 191, 875, 169, 476, 528, 833, 601, 279, 567, 523, 552, 890, 776, 752, 220, 613, 980, 720, 363, 421, 425, 350, 760, 377, 541, 337, 981, 755, 294, 264, 274, 599, 379, 208, 769, 380, 398, 202, 619, 928, 643, 918, 677, 291, 277, 390, 381, 310, 428, 134, 563, 171, 718, 561, 627, 699, 164, 947, 620, 607, 994, 188, 751, 120, 731, 710, 682, 609, 475, 852, 156, 486, 559, 419, 845, 904, 901, 957, 680, 997, 339, 124, 474, 142, 531, 221, 203, 492, 670, 568, 806, 830, 394, 165, 376, 248, 365, 787, 589, 952, 426, 693, 596, 611, 469, 608, 354, 654, 158, 697, 885, 325, 554, 382, 914, 161, 516, 603, 658, 818, 301, 785, 592, 271, 781, 565, 638, 384, 495, 887, 490, 805, 353, 986, 387, 809, 586, 647
Uns interessieren jetzt zwei Fragen: Wie oft wird die Funktion heapify eigentlich aufgerufen und wie oft wird in ihr ein Element vertauscht?
A sei die Anzahl der Aufrufe der Funktion heapify.
B sei die Anzahl der Vertauschungen in der Funktion heapify.
Gesucht ist nun eine Lösungszahl, die ganz einfach berechnet werden kann:
Lösungszahl = A + B
Wenn ihr diese Zahl bei certitudes.org eingebt, erhaltet ihr die Koordinaten der Dose und könnt schon mal eins der tausend Verstecke aufsuchen :-)
Da es hier einen Bonus bei dieser Cacheserie gibt, notiert euch bitte die Bonuszahl, falls ihr auch noch diese Dose finden möchtet. Viel Spaß beim rätseln, rechnen, suchen und loggen! Es ist möglich diese Serie auch als Wanderung anzugehen - was ich übrigens auch empfehle. Die Wegstrecke beträgt etwa 5km. Benutzt dafür den angegebenen Parkplatz. Ich empfehle euch dabei die Caches in der Reihenfolge (Chaos 5, Chaos 1, Chaos 2, Chaos 4, Chaos 3 und Chaos Bonus) anzugehen.