二叉树（二） - 二叉堆

• • 1.什么是二叉堆
  • 2.二叉堆的基本操作
  • 2.2 提取最大（最小）值
  • 3.二叉堆应用-堆排序
  • 3.写在最后

1.什么是二叉堆

二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

上图说:

可以看出，这是一颗完全二叉树,同时这也是一个最大堆。
值得一提的是，完全二叉树具有以下性质，在之后的分析中会使用到:

• 结点i的父结点为结点(i-1)/2 （注意这里是地板除法，举个栗子，在C/JAVA…语言中 直接另1/2等于0，而不是0.5。具体可以这样写floor(1/2)也就是将1/2的结果在向下取整。）
• 结点i的子结点分别为(2*i+1)和(2*i-1)

同时，基于完全二叉树的特性，二叉堆通常使用数组来编写。

2.二叉堆的基本操作

二叉堆的基本操作为插入，提取最大（最小）值。

2.1插入

在上面的二叉堆中，我们插入了55这个节点。
我们来分析下，它是如何插入到这个二叉堆中的：

• 首先按照完全二叉树的顺序，我们在编号12这个地方生成55这个节点
• 接着，由于这是一个最大二叉堆，所以要比较它的父节点（如果有的话）和它的大小，这里55是大于7的，所以两个交换了位置
• 循环第2步，直到它的父亲节点不比它大，或者已经达到根节点。

从上面三步分析中，我们可以直到发生，一个插入的操作无非就是：生成-循环比较-判定终止条件三步。所以我们可以写出下面的代码(python):

def insert(binaryHeap, i):
    binaryHeap.append(i)
    flag = 0
    index = len(binaryHeap) - 1
    while not flag and index:
        parent = binaryHeap[(index - 1) // 2]
        if parent < binaryHeap[index]:
            # 交换
            binaryHeap = swap(binaryHeap, index, (index - 1) // 2)
            # 更新节点位置
            index = (index - 1) // 2
        else:
            flag = 1
    return binaryHeap

知道怎么插入节点了，那么我们能够运用它来做什么呢？（废话，当然是插入操作了），其实最简单的我们可以用它来生成二叉堆。
为了加深印象，我再贴一张，生成二叉堆动态的图:

# 生成二叉堆
def createBinaryHeap(originData):
    if len(originData) is 0:
        print("当前数据为空")
        return
    binaryHeapData = [originData[0]]
    for each in originData[1:]:
        binaryHeapData = insert(binaryHeapData, each)
    return binaryHeapData

2.2 提取最大（最小）值

最大（最小）堆的根节点，代表了这个堆中的最大（最小）值，将它进行弹出，在把整棵树最后的节点放置到根节点，再把它交换到恰当的位置，这就是提取操作。

表达的不是很好，所以还是贴图吧

相信你已经能够理解什么是提取操作了。
那么下面看代码:

def deleteTop(binaryHeap):
    # 将最后的元素提取到最前面来
    if len(binaryHeap) is 0:
        print("当前堆以为0")
        return

    top = binaryHeap[0]
    if len(binaryHeap) == 1:
        binaryHeap.pop()
        return (top, binaryHeap)

    binaryHeap[0] = binaryHeap.pop()
    index = 0
    num = len(binaryHeap) - 1
    over = 0

    while index < num and not over:
        left_son = index * 2 + 1
        right_son = index * 2 + 2
        flag = 0
        if left_son <= num:
            # 有左孩子
            if right_son <= num:
                # 有右孩子
                max_son = left_son if binaryHeap[left_son] > binaryHeap[right_son] else right_son
                if binaryHeap[index] < binaryHeap[max_son]:
                    binaryHeap = swap(binaryHeap, index, max_son)
                    flag = 1
                    index = max_son
            else:
                # 没有右孩子，只比较父亲和左孩子
                if binaryHeap[index] < binaryHeap[left_son]:
                    binaryHeap = swap(binaryHeap, index, left_son)
                    flag = 1
                    index = left_son
            if flag is not 1:
                over = 1
        else:
            # 没有孩子
            over = 1
    return (top, binaryHeap)

那么提取操作能做什么呢？没错，就是今天的应用-堆排序

3.二叉堆应用-堆排序

所谓的堆排序，也就是利用了二叉堆本身性质，在循环调用提取操作的一种排序方式，其平均时间复杂度为O(nlogn)，是一种排序效率很高的排序方法。
还是老规矩，先上图：

贴上代码:

def HeapSort(data):
    # 堆排序
    length = len(data)
    sort = [-1] * length
    for i in range(length):
        (sort[i], data) = deleteTop(data)
    return sort

为了说明堆排序的高效性，我对1000个随机数据，分别采用了堆排序，选择排序和冒泡排序来做对比。

[880, 475, 897, 535, 379, 905, 915, 924, 944, 876, 404, 636, 257, 43, 969, 537, 718, 104, 662, 701, 399, 574, 825, 574, 888, 802, 806, 689, 173, 571, 923, 21, 701, 789, 251, 137, 409, 925, 825, 809, 524, 404, 765, 754, 320, 717, 41, 187, 721, 874, 553, 590, 188, 465, 417, 812, 649, 709, 615, 283, 332, 511, 387, 983, 778, 601, 789, 181, 772, 499, 687, 920, 877, 36, 275, 435, 698, 33, 772, 38, 947, 669, 739, 783, 400, 559, 94, 564, 230, 935, 507, 811, 56, 934, 747, 381, 279, 479, 91, 815, 148, 89, 162, 993, 444, 962, 774, 878, 494, 789, 346, 437, 38, 836, 754, 210, 964, 973, 936, 534, 308, 600, 352, 276, 574, 871, 918, 878, 414, 964, 572, 317, 404, 704, 935, 338, 405, 955, 767, 102, 768, 180, 436, 208, 515, 110, 873, 859, 1000, 78, 580, 606, 311, 566, 35, 169, 937, 882, 700, 913, 781, 10, 445, 723, 560, 254, 879, 546, 95, 631, 472, 827, 683, 740, 407, 282, 54, 687, 392, 438, 987, 14, 271, 913, 643, 957, 372, 132, 556, 107, 629, 588, 62, 506, 2, 245, 366, 687, 624, 645, 952, 595, 566, 219, 592, 595, 622, 919, 57, 258, 710, 105, 31, 421, 308, 641, 470, 861, 87, 74, 704, 880, 920, 575, 30, 698, 942, 123, 414, 606, 698, 511, 413, 100, 777, 698, 634, 475, 918, 332, 36, 768, 402, 919, 777, 789, 874, 375, 888, 189, 85, 802, 136, 492, 277, 706, 463, 839, 622, 623, 976, 157, 764, 229, 980, 612, 38, 389, 891, 885, 888, 121, 723, 642, 606, 571, 933, 872, 71, 622, 103, 276, 153, 123, 921, 740, 163, 626, 455, 347, 827, 229, 613, 596, 689, 698, 658, 738, 434, 319, 552, 751, 155, 673, 363, 210, 983, 365, 698, 264, 414, 247, 75, 891, 266, 133, 533, 11, 320, 41, 489, 96, 809, 445, 613, 606, 658, 497, 652, 931, 800, 473, 726, 475, 196, 660, 528, 355, 840, 24, 928, 446, 951, 443, 478, 76, 856, 156, 995, 877, 548, 945, 445, 632, 58, 963, 522, 553, 793, 599, 552, 971, 439, 467, 809, 537, 835, 220, 707, 495, 450, 370, 13, 112, 397, 512, 643, 974, 25, 274, 339, 569, 666, 270, 45, 647, 630, 859, 872, 456, 628, 897, 546, 629, 156, 715, 334, 988, 447, 940, 122, 514, 438, 209, 590, 893, 565, 282, 712, 500, 938, 968, 406, 385, 633, 198, 274, 33, 752, 554, 184, 637, 260, 51, 170, 792, 160, 239, 615, 848, 866, 570, 483, 291, 401, 370, 821, 290, 118, 819, 229, 157, 31, 1, 706, 439, 589, 125, 969, 93, 150, 394, 967, 832, 641, 830, 446, 149, 428, 394, 338, 556, 913, 435, 301, 999, 83, 248, 254, 457, 785, 748, 757, 408, 582, 101, 714, 959, 531, 172, 802, 158, 419, 150, 456, 678, 638, 429, 965, 85, 700, 997, 88, 296, 144, 507, 683, 299, 951, 544, 646, 419, 496, 505, 982, 322, 565, 285, 627, 93, 247, 910, 594, 484, 943, 710, 315, 685, 584, 965, 129, 726, 527, 913, 509, 438, 22, 727, 860, 776, 120, 511, 810, 603, 693, 323, 161, 445, 451, 305, 685, 393, 218, 772, 125, 924, 945, 449, 917, 661, 149, 109, 788, 945, 883, 186, 158, 470, 319, 673, 427, 694, 357, 106, 899, 226, 874, 481, 18, 712, 50, 969, 612, 693, 236, 584, 938, 716, 228, 169, 95, 20, 302, 969, 77, 773, 723, 979, 247, 30, 345, 189, 335, 155, 391, 531, 785, 55, 746, 474, 122, 606, 103, 96, 76, 536, 430, 986, 612, 21, 558, 230, 372, 537, 315, 662, 623, 123, 975, 650, 181, 651, 431, 622, 566, 798, 255, 704, 464, 852, 888, 913, 145, 544, 516, 807, 659, 432, 844, 537, 71, 969, 102, 367, 745, 935, 954, 687, 789, 890, 794, 425, 760, 445, 953, 940, 251, 383, 302, 754, 861, 97, 792, 618, 620, 208, 934, 720, 864, 495, 240, 363, 224, 277, 497, 176, 659, 922, 554, 818, 156, 867, 385, 19, 901, 228, 258, 684, 36, 20, 430, 106, 322, 417, 56, 628, 357, 155, 452, 961, 858, 857, 806, 318, 373, 297, 904, 598, 818, 146, 402, 800, 797, 535, 289, 596, 805, 215, 209, 888, 501, 236, 979, 680, 366, 761, 114, 549, 565, 344, 774, 301, 931, 852, 194, 189, 569, 670, 673, 407, 473, 422, 583, 605, 95, 245, 775, 746, 724, 456, 975, 894, 14, 442, 626, 78, 689, 366, 487, 12, 15, 578, 845, 900, 322, 54, 584, 510, 686, 108, 448, 252, 140, 315, 849, 125, 546, 104, 930, 915, 683, 88, 483, 301, 162, 979, 33, 512, 513, 791, 496, 262, 46, 882, 987, 808, 918, 322, 825, 359, 832, 274, 393, 12, 43, 521, 927, 980, 254, 585, 788, 563, 932, 96, 869, 32, 43, 670, 898, 263, 289, 112, 422, 545, 297, 230, 758, 512, 702, 227, 295, 714, 702, 286, 74, 823, 13, 81, 26, 256, 453, 20, 365, 588, 571, 139, 60, 294, 688, 997, 123, 644, 494, 13, 142, 557, 593, 909, 755, 484, 282, 266, 751, 23, 821, 82, 108, 529, 42, 609, 194, 326, 148, 697, 249, 627, 495, 619, 736, 235, 291, 100, 923, 935, 80, 534, 405, 5, 875, 256, 959, 728, 624, 140, 812, 857, 946, 447, 86, 600, 77, 627, 941, 354, 289, 647, 726, 240, 812, 560, 881, 266, 556, 753, 762, 586, 265, 695, 933, 789, 123, 810, 628, 129, 335, 861, 772, 629, 802, 584, 534, 253, 185, 415, 31, 189, 112, 549, 369, 908, 967, 765, 322, 802, 112, 356, 299, 774, 349, 483, 287, 706, 963, 234, 819, 687, 557, 520, 934, 291, 184, 540, 843, 829, 509, 13, 459, 115, 502, 467, 397, 353, 457, 174, 535, 126, 143, 243, 746, 873, 714, 746, 306, 507, 6, 368, 708, 892, 630, 274, 695, 150, 142, 975, 358, 464, 794, 641, 895, 898]
排序结果:
[1, 2, 5, 6, 10, 11, 12, 12, 13, 13, 13, 13, 14, 14, 15, 18, 19, 20, 20, 20, 21, 21, 22, 23, 24, 25, 26, 30, 30, 31, 31, 31, 32, 33, 33, 33, 35, 36, 36, 36, 38, 38, 38, 41, 41, 42, 43, 43, 43, 45, 46, 50, 51, 54, 54, 55, 56, 56, 57, 58, 60, 62, 71, 71, 74, 74, 75, 76, 76, 77, 77, 78, 78, 80, 81, 82, 83, 85, 85, 86, 87, 88, 88, 89, 91, 93, 93, 94, 95, 95, 95, 96, 96, 96, 97, 100, 100, 101, 102, 102, 103, 103, 104, 104, 105, 106, 106, 107, 108, 108, 109, 110, 112, 112, 112, 112, 114, 115, 118, 120, 121, 122, 122, 123, 123, 123, 123, 123, 125, 125, 125, 126, 129, 129, 132, 133, 136, 137, 139, 140, 140, 142, 142, 143, 144, 145, 146, 148, 148, 149, 149, 150, 150, 150, 153, 155, 155, 155, 156, 156, 156, 157, 157, 158, 158, 160, 161, 162, 162, 163, 169, 169, 170, 172, 173, 174, 176, 180, 181, 181, 184, 184, 185, 186, 187, 188, 189, 189, 189, 189, 194, 194, 196, 198, 208, 208, 209, 209, 210, 210, 215, 218, 219, 220, 224, 226, 227, 228, 228, 229, 229, 229, 230, 230, 230, 234, 235, 236, 236, 239, 240, 240, 243, 245, 245, 247, 247, 247, 248, 249, 251, 251, 252, 253, 254, 254, 254, 255, 256, 256, 257, 258, 258, 260, 262, 263, 264, 265, 266, 266, 266, 270, 271, 274, 274, 274, 274, 275, 276, 276, 277, 277, 279, 282, 282, 282, 283, 285, 286, 287, 289, 289, 289, 290, 291, 291, 291, 294, 295, 296, 297, 297, 299, 299, 301, 301, 301, 302, 302, 305, 306, 308, 308, 311, 315, 315, 315, 317, 318, 319, 319, 320, 320, 322, 322, 322, 322, 322, 323, 326, 332, 332, 334, 335, 335, 338, 338, 339, 344, 345, 346, 347, 349, 352, 353, 354, 355, 356, 357, 357, 358, 359, 363, 363, 365, 365, 366, 366, 366, 367, 368, 369, 370, 370, 372, 372, 373, 375, 379, 381, 383, 385, 385, 387, 389, 391, 392, 393, 393, 394, 394, 397, 397, 399, 400, 401, 402, 402, 404, 404, 404, 405, 405, 406, 407, 407, 408, 409, 413, 414, 414, 414, 415, 417, 417, 419, 419, 421, 422, 422, 425, 427, 428, 429, 430, 430, 431, 432, 434, 435, 435, 436, 437, 438, 438, 438, 439, 439, 442, 443, 444, 445, 445, 445, 445, 445, 446, 446, 447, 447, 448, 449, 450, 451, 452, 453, 455, 456, 456, 456, 457, 457, 459, 463, 464, 464, 465, 467, 467, 470, 470, 472, 473, 473, 474, 475, 475, 475, 478, 479, 481, 483, 483, 483, 484, 484, 487, 489, 492, 494, 494, 495, 495, 495, 496, 496, 497, 497, 499, 500, 501, 502, 505, 506, 507, 507, 507, 509, 509, 510, 511, 511, 511, 512, 512, 512, 513, 514, 515, 516, 520, 521, 522, 524, 527, 528, 529, 531, 531, 533, 534, 534, 534, 535, 535, 535, 536, 537, 537, 537, 537, 540, 544, 544, 545, 546, 546, 546, 548, 549, 549, 552, 552, 553, 553, 554, 554, 556, 556, 556, 557, 557, 558, 559, 560, 560, 563, 564, 565, 565, 565, 566, 566, 566, 569, 569, 570, 571, 571, 571, 572, 574, 574, 574, 575, 578, 580, 582, 583, 584, 584, 584, 584, 585, 586, 588, 588, 589, 590, 590, 592, 593, 594, 595, 595, 596, 596, 598, 599, 600, 600, 601, 603, 605, 606, 606, 606, 606, 606, 609, 612, 612, 612, 613, 613, 615, 615, 618, 619, 620, 622, 622, 622, 622, 623, 623, 624, 624, 626, 626, 627, 627, 627, 628, 628, 628, 629, 629, 629, 630, 630, 631, 632, 633, 634, 636, 637, 638, 641, 641, 641, 642, 643, 643, 644, 645, 646, 647, 647, 649, 650, 651, 652, 658, 658, 659, 659, 660, 661, 662, 662, 666, 669, 670, 670, 673, 673, 673, 678, 680, 683, 683, 683, 684, 685, 685, 686, 687, 687, 687, 687, 687, 688, 689, 689, 689, 693, 693, 694, 695, 695, 697, 698, 698, 698, 698, 698, 698, 700, 700, 701, 701, 702, 702, 704, 704, 704, 706, 706, 706, 707, 708, 709, 710, 710, 712, 712, 714, 714, 714, 715, 716, 717, 718, 720, 721, 723, 723, 723, 724, 726, 726, 726, 727, 728, 736, 738, 739, 740, 740, 745, 746, 746, 746, 746, 747, 748, 751, 751, 752, 753, 754, 754, 754, 755, 757, 758, 760, 761, 762, 764, 765, 765, 767, 768, 768, 772, 772, 772, 772, 773, 774, 774, 774, 775, 776, 777, 777, 778, 781, 783, 785, 785, 788, 788, 789, 789, 789, 789, 789, 789, 791, 792, 792, 793, 794, 794, 797, 798, 800, 800, 802, 802, 802, 802, 802, 805, 806, 806, 807, 808, 809, 809, 809, 810, 810, 811, 812, 812, 812, 815, 818, 818, 819, 819, 821, 821, 823, 825, 825, 825, 827, 827, 829, 830, 832, 832, 835, 836, 839, 840, 843, 844, 845, 848, 849, 852, 852, 856, 857, 857, 858, 859, 859, 860, 861, 861, 861, 864, 866, 867, 869, 871, 872, 872, 873, 873, 874, 874, 874, 875, 876, 877, 877, 878, 878, 879, 880, 880, 881, 882, 882, 883, 885, 888, 888, 888, 888, 888, 890, 891, 891, 892, 893, 894, 895, 897, 897, 898, 898, 899, 900, 901, 904, 905, 908, 909, 910, 913, 913, 913, 913, 913, 915, 915, 917, 918, 918, 918, 919, 919, 920, 920, 921, 922, 923, 923, 924, 924, 925, 927, 928, 930, 931, 931, 932, 933, 933, 934, 934, 934, 935, 935, 935, 935, 936, 937, 938, 938, 940, 940, 941, 942, 943, 944, 945, 945, 945, 946, 947, 951, 951, 952, 953, 954, 955, 957, 959, 959, 961, 962, 963, 963, 964, 964, 965, 965, 967, 967, 968, 969, 969, 969, 969, 969, 971, 973, 974, 975, 975, 975, 976, 979, 979, 979, 980, 980, 982, 983, 983, 986, 987, 987, 988, 993, 995, 997, 997, 999, 1000]
堆排耗时： 0.036165414852166435
[1, 2, 5, 6, 10, 11, 12, 12, 13, 13, 13, 13, 14, 14, 15, 18, 19, 20, 20, 20, 21, 21, 22, 23, 24, 25, 26, 30, 30, 31, 31, 31, 32, 33, 33, 33, 35, 36, 36, 36, 38, 38, 38, 41, 41, 42, 43, 43, 43, 45, 46, 50, 51, 54, 54, 55, 56, 56, 57, 58, 60, 62, 71, 71, 74, 74, 75, 76, 76, 77, 77, 78, 78, 80, 81, 82, 83, 85, 85, 86, 87, 88, 88, 89, 91, 93, 93, 94, 95, 95, 95, 96, 96, 96, 97, 100, 100, 101, 102, 102, 103, 103, 104, 104, 105, 106, 106, 107, 108, 108, 109, 110, 112, 112, 112, 112, 114, 115, 118, 120, 121, 122, 122, 123, 123, 123, 123, 123, 125, 125, 125, 126, 129, 129, 132, 133, 136, 137, 139, 140, 140, 142, 142, 143, 144, 145, 146, 148, 148, 149, 149, 150, 150, 150, 153, 155, 155, 155, 156, 156, 156, 157, 157, 158, 158, 160, 161, 162, 162, 163, 169, 169, 170, 172, 173, 174, 176, 180, 181, 181, 184, 184, 185, 186, 187, 188, 189, 189, 189, 189, 194, 194, 196, 198, 208, 208, 209, 209, 210, 210, 215, 218, 219, 220, 224, 226, 227, 228, 228, 229, 229, 229, 230, 230, 230, 234, 235, 236, 236, 239, 240, 240, 243, 245, 245, 247, 247, 247, 248, 249, 251, 251, 252, 253, 254, 254, 254, 255, 256, 256, 257, 258, 258, 260, 262, 263, 264, 265, 266, 266, 266, 270, 271, 274, 274, 274, 274, 275, 276, 276, 277, 277, 279, 282, 282, 282, 283, 285, 286, 287, 289, 289, 289, 290, 291, 291, 291, 294, 295, 296, 297, 297, 299, 299, 301, 301, 301, 302, 302, 305, 306, 308, 308, 311, 315, 315, 315, 317, 318, 319, 319, 320, 320, 322, 322, 322, 322, 322, 323, 326, 332, 332, 334, 335, 335, 338, 338, 339, 344, 345, 346, 347, 349, 352, 353, 354, 355, 356, 357, 357, 358, 359, 363, 363, 365, 365, 366, 366, 366, 367, 368, 369, 370, 370, 372, 372, 373, 375, 379, 381, 383, 385, 385, 387, 389, 391, 392, 393, 393, 394, 394, 397, 397, 399, 400, 401, 402, 402, 404, 404, 404, 405, 405, 406, 407, 407, 408, 409, 413, 414, 414, 414, 415, 417, 417, 419, 419, 421, 422, 422, 425, 427, 428, 429, 430, 430, 431, 432, 434, 435, 435, 436, 437, 438, 438, 438, 439, 439, 442, 443, 444, 445, 445, 445, 445, 445, 446, 446, 447, 447, 448, 449, 450, 451, 452, 453, 455, 456, 456, 456, 457, 457, 459, 463, 464, 464, 465, 467, 467, 470, 470, 472, 473, 473, 474, 475, 475, 475, 478, 479, 481, 483, 483, 483, 484, 484, 487, 489, 492, 494, 494, 495, 495, 495, 496, 496, 497, 497, 499, 500, 501, 502, 505, 506, 507, 507, 507, 509, 509, 510, 511, 511, 511, 512, 512, 512, 513, 514, 515, 516, 520, 521, 522, 524, 527, 528, 529, 531, 531, 533, 534, 534, 534, 535, 535, 535, 536, 537, 537, 537, 537, 540, 544, 544, 545, 546, 546, 546, 548, 549, 549, 552, 552, 553, 553, 554, 554, 556, 556, 556, 557, 557, 558, 559, 560, 560, 563, 564, 565, 565, 565, 566, 566, 566, 569, 569, 570, 571, 571, 571, 572, 574, 574, 574, 575, 578, 580, 582, 583, 584, 584, 584, 584, 585, 586, 588, 588, 589, 590, 590, 592, 593, 594, 595, 595, 596, 596, 598, 599, 600, 600, 601, 603, 605, 606, 606, 606, 606, 606, 609, 612, 612, 612, 613, 613, 615, 615, 618, 619, 620, 622, 622, 622, 622, 623, 623, 624, 624, 626, 626, 627, 627, 627, 628, 628, 628, 629, 629, 629, 630, 630, 631, 632, 633, 634, 636, 637, 638, 641, 641, 641, 642, 643, 643, 644, 645, 646, 647, 647, 649, 650, 651, 652, 658, 658, 659, 659, 660, 661, 662, 662, 666, 669, 670, 670, 673, 673, 673, 678, 680, 683, 683, 683, 684, 685, 685, 686, 687, 687, 687, 687, 687, 688, 689, 689, 689, 693, 693, 694, 695, 695, 697, 698, 698, 698, 698, 698, 698, 700, 700, 701, 701, 702, 702, 704, 704, 704, 706, 706, 706, 707, 708, 709, 710, 710, 712, 712, 714, 714, 714, 715, 716, 717, 718, 720, 721, 723, 723, 723, 724, 726, 726, 726, 727, 728, 736, 738, 739, 740, 740, 745, 746, 746, 746, 746, 747, 748, 751, 751, 752, 753, 754, 754, 754, 755, 757, 758, 760, 761, 762, 764, 765, 765, 767, 768, 768, 772, 772, 772, 772, 773, 774, 774, 774, 775, 776, 777, 777, 778, 781, 783, 785, 785, 788, 788, 789, 789, 789, 789, 789, 789, 791, 792, 792, 793, 794, 794, 797, 798, 800, 800, 802, 802, 802, 802, 802, 805, 806, 806, 807, 808, 809, 809, 809, 810, 810, 811, 812, 812, 812, 815, 818, 818, 819, 819, 821, 821, 823, 825, 825, 825, 827, 827, 829, 830, 832, 832, 835, 836, 839, 840, 843, 844, 845, 848, 849, 852, 852, 856, 857, 857, 858, 859, 859, 860, 861, 861, 861, 864, 866, 867, 869, 871, 872, 872, 873, 873, 874, 874, 874, 875, 876, 877, 877, 878, 878, 879, 880, 880, 881, 882, 882, 883, 885, 888, 888, 888, 888, 888, 890, 891, 891, 892, 893, 894, 895, 897, 897, 898, 898, 899, 900, 901, 904, 905, 908, 909, 910, 913, 913, 913, 913, 913, 915, 915, 917, 918, 918, 918, 919, 919, 920, 920, 921, 922, 923, 923, 924, 924, 925, 927, 928, 930, 931, 931, 932, 933, 933, 934, 934, 934, 935, 935, 935, 935, 936, 937, 938, 938, 940, 940, 941, 942, 943, 944, 945, 945, 945, 946, 947, 951, 951, 952, 953, 954, 955, 957, 959, 959, 961, 962, 963, 963, 964, 964, 965, 965, 967, 967, 968, 969, 969, 969, 969, 969, 971, 973, 974, 975, 975, 975, 976, 979, 979, 979, 980, 980, 982, 983, 983, 986, 987, 987, 988, 993, 995, 997, 997, 999, 1000]
冒泡耗时： 0.45751492833160634
[1, 2, 5, 6, 10, 11, 12, 12, 13, 13, 13, 13, 14, 14, 15, 18, 19, 20, 20, 20, 21, 21, 22, 23, 24, 25, 26, 30, 30, 31, 31, 31, 32, 33, 33, 33, 35, 36, 36, 36, 38, 38, 38, 41, 41, 42, 43, 43, 43, 45, 46, 50, 51, 54, 54, 55, 56, 56, 57, 58, 60, 62, 71, 71, 74, 74, 75, 76, 76, 77, 77, 78, 78, 80, 81, 82, 83, 85, 85, 86, 87, 88, 88, 89, 91, 93, 93, 94, 95, 95, 95, 96, 96, 96, 97, 100, 100, 101, 102, 102, 103, 103, 104, 104, 105, 106, 106, 107, 108, 108, 109, 110, 112, 112, 112, 112, 114, 115, 118, 120, 121, 122, 122, 123, 123, 123, 123, 123, 125, 125, 125, 126, 129, 129, 132, 133, 136, 137, 139, 140, 140, 142, 142, 143, 144, 145, 146, 148, 148, 149, 149, 150, 150, 150, 153, 155, 155, 155, 156, 156, 156, 157, 157, 158, 158, 160, 161, 162, 162, 163, 169, 169, 170, 172, 173, 174, 176, 180, 181, 181, 184, 184, 185, 186, 187, 188, 189, 189, 189, 189, 194, 194, 196, 198, 208, 208, 209, 209, 210, 210, 215, 218, 219, 220, 224, 226, 227, 228, 228, 229, 229, 229, 230, 230, 230, 234, 235, 236, 236, 239, 240, 240, 243, 245, 245, 247, 247, 247, 248, 249, 251, 251, 252, 253, 254, 254, 254, 255, 256, 256, 257, 258, 258, 260, 262, 263, 264, 265, 266, 266, 266, 270, 271, 274, 274, 274, 274, 275, 276, 276, 277, 277, 279, 282, 282, 282, 283, 285, 286, 287, 289, 289, 289, 290, 291, 291, 291, 294, 295, 296, 297, 297, 299, 299, 301, 301, 301, 302, 302, 305, 306, 308, 308, 311, 315, 315, 315, 317, 318, 319, 319, 320, 320, 322, 322, 322, 322, 322, 323, 326, 332, 332, 334, 335, 335, 338, 338, 339, 344, 345, 346, 347, 349, 352, 353, 354, 355, 356, 357, 357, 358, 359, 363, 363, 365, 365, 366, 366, 366, 367, 368, 369, 370, 370, 372, 372, 373, 375, 379, 381, 383, 385, 385, 387, 389, 391, 392, 393, 393, 394, 394, 397, 397, 399, 400, 401, 402, 402, 404, 404, 404, 405, 405, 406, 407, 407, 408, 409, 413, 414, 414, 414, 415, 417, 417, 419, 419, 421, 422, 422, 425, 427, 428, 429, 430, 430, 431, 432, 434, 435, 435, 436, 437, 438, 438, 438, 439, 439, 442, 443, 444, 445, 445, 445, 445, 445, 446, 446, 447, 447, 448, 449, 450, 451, 452, 453, 455, 456, 456, 456, 457, 457, 459, 463, 464, 464, 465, 467, 467, 470, 470, 472, 473, 473, 474, 475, 475, 475, 478, 479, 481, 483, 483, 483, 484, 484, 487, 489, 492, 494, 494, 495, 495, 495, 496, 496, 497, 497, 499, 500, 501, 502, 505, 506, 507, 507, 507, 509, 509, 510, 511, 511, 511, 512, 512, 512, 513, 514, 515, 516, 520, 521, 522, 524, 527, 528, 529, 531, 531, 533, 534, 534, 534, 535, 535, 535, 536, 537, 537, 537, 537, 540, 544, 544, 545, 546, 546, 546, 548, 549, 549, 552, 552, 553, 553, 554, 554, 556, 556, 556, 557, 557, 558, 559, 560, 560, 563, 564, 565, 565, 565, 566, 566, 566, 569, 569, 570, 571, 571, 571, 572, 574, 574, 574, 575, 578, 580, 582, 583, 584, 584, 584, 584, 585, 586, 588, 588, 589, 590, 590, 592, 593, 594, 595, 595, 596, 596, 598, 599, 600, 600, 601, 603, 605, 606, 606, 606, 606, 606, 609, 612, 612, 612, 613, 613, 615, 615, 618, 619, 620, 622, 622, 622, 622, 623, 623, 624, 624, 626, 626, 627, 627, 627, 628, 628, 628, 629, 629, 629, 630, 630, 631, 632, 633, 634, 636, 637, 638, 641, 641, 641, 642, 643, 643, 644, 645, 646, 647, 647, 649, 650, 651, 652, 658, 658, 659, 659, 660, 661, 662, 662, 666, 669, 670, 670, 673, 673, 673, 678, 680, 683, 683, 683, 684, 685, 685, 686, 687, 687, 687, 687, 687, 688, 689, 689, 689, 693, 693, 694, 695, 695, 697, 698, 698, 698, 698, 698, 698, 700, 700, 701, 701, 702, 702, 704, 704, 704, 706, 706, 706, 707, 708, 709, 710, 710, 712, 712, 714, 714, 714, 715, 716, 717, 718, 720, 721, 723, 723, 723, 724, 726, 726, 726, 727, 728, 736, 738, 739, 740, 740, 745, 746, 746, 746, 746, 747, 748, 751, 751, 752, 753, 754, 754, 754, 755, 757, 758, 760, 761, 762, 764, 765, 765, 767, 768, 768, 772, 772, 772, 772, 773, 774, 774, 774, 775, 776, 777, 777, 778, 781, 783, 785, 785, 788, 788, 789, 789, 789, 789, 789, 789, 791, 792, 792, 793, 794, 794, 797, 798, 800, 800, 802, 802, 802, 802, 802, 805, 806, 806, 807, 808, 809, 809, 809, 810, 810, 811, 812, 812, 812, 815, 818, 818, 819, 819, 821, 821, 823, 825, 825, 825, 827, 827, 829, 830, 832, 832, 835, 836, 839, 840, 843, 844, 845, 848, 849, 852, 852, 856, 857, 857, 858, 859, 859, 860, 861, 861, 861, 864, 866, 867, 869, 871, 872, 872, 873, 873, 874, 874, 874, 875, 876, 877, 877, 878, 878, 879, 880, 880, 881, 882, 882, 883, 885, 888, 888, 888, 888, 888, 890, 891, 891, 892, 893, 894, 895, 897, 897, 898, 898, 899, 900, 901, 904, 905, 908, 909, 910, 913, 913, 913, 913, 913, 915, 915, 917, 918, 918, 918, 919, 919, 920, 920, 921, 922, 923, 923, 924, 924, 925, 927, 928, 930, 931, 931, 932, 933, 933, 934, 934, 934, 935, 935, 935, 935, 936, 937, 938, 938, 940, 940, 941, 942, 943, 944, 945, 945, 945, 946, 947, 951, 951, 952, 953, 954, 955, 957, 959, 959, 961, 962, 963, 963, 964, 964, 965, 965, 967, 967, 968, 969, 969, 969, 969, 969, 971, 973, 974, 975, 975, 975, 976, 979, 979, 979, 980, 980, 982, 983, 983, 986, 987, 987, 988, 993, 995, 997, 997, 999, 1000]
选择耗时： 0.16573644796584242

从时间上看，堆排序明显小于其他两种排序，数据越大，这种差异越大。

3.写在最后

嗯，二叉堆差不多就这么多了，我也算是现学现卖吧，下次准备写二叉搜索树。

持续更新中…
二叉树（一）-基本知识