Python堆排序原理與實現方法詳解

本文實例講述了Python堆排序原理與實現方法。分享給大家供大家參考，具體如下：

在這里要事先說明一下我也是新手，很多東西我了解不是很深入，寫算法完全是鍛煉自己邏輯能力同時順帶幫助讀研的朋友么解決一些實際問題。所以很多時候考慮的東西不是很全面能請各位看到博文的大牛們指正。對于排序算法說實在的我覺得已經寫爛了，但是為什么還是要過一遍呢？還是為了能夠打牢基礎。說一下自己的看法，對于已經的玩爛的算法因該怎么學。首先最重要的還是了解算法的基本模型和算法思想，我覺得這是非常重要的。其次的話首先先嘗試自己實現算法每個步驟的功能，當遇到瓶頸的時候回去看算法思想。當你寫出來的時候就應該去網上找找有沒有更好的實現方法。編程最大的魅力在于每個人都有每個人的套路。然后去思考自己還有哪些地方寫的不夠好。寫算法實際上目標只有兩個，對基礎語法的鞏固和對算法思想的理解。

堆排序

堆

在這里首先要先解釋一下什么是堆，堆棧是計算機的兩種最基本的數據結構。堆的特點就是FIFO(first in first out)先進先出，這里的話我覺得可以理解成樹的結構。堆在接收數據的時候先接收的數據會被先彈出。

棧的特性正好與堆相反，是屬于FILO(first in/last out)先進后出的類型。棧處于一級緩存而堆處于二級緩存中。這個不是本文重點所以不做過多展開。

堆排序節點訪問和操作定義

堆節點的訪問

在這里我們借用wiki的定義來說明：

通常堆是通過一維數組來實現的。在陣列起始位置為0的情況中

(1)父節點i的左子節點在位置(2*i+1);
(2)父節點i的右子節點在位置(2*i+2);
(3)子節點i的父節點在位置floor((i-1)/2);

堆操作

堆可以分為大根堆和小根堆，這里用最大堆的情況來定義操作:

(1)最大堆調整(MAX_Heapify):將堆的末端子節點作調整，使得子節點永遠小于父節點。這是核心步驟，在建堆和堆排序都會用到。比較i的根節點和與其所對應i的孩子節點的值。當i根節點的值比左孩子節點的值要小的時候，就把i根節點和左孩子節點所對應的值交換，當i根節點的值比右孩子的節點所對應的值要小的時候，就把i根節點和右孩子節點所對應的值交換。然后再調用堆調整這個過程，可見這是一個遞歸的過程。

(2)建立最大堆(Build_Max_Heap):將堆所有數據重新排序。建堆的過程其實就是不斷做最大堆調整的過程，從len/2出開始調整，一直比到第一個節點。

(3)堆排序(HeapSort):移除位在第一個數據的根節點，并做最大堆調整的遞歸運算。堆排序是利用建堆和堆調整來進行的。首先先建堆，然后將堆的根節點選出與最后一個節點進行交換，然后將前面len-1個節點繼續做堆調整的過程。直到將所有的節點取出，對于n個數我們只需要做n-1次操作。

這里用網上的一張直觀圖來感受一下

代碼：

# -*- coding: utf-8 -*-
#! python2
import random
def MAX_Heapify(heap,HeapSize,root):#在堆中做結構調整使得父節點的值大于子節點
  left = 2*root + 1
  right = left + 1
  larger = root
  if left < HeapSize and heap[larger] < heap[left]:
    larger = left
  if right < HeapSize and heap[larger] < heap[right]:
    larger = right
  if larger != root:#如果做了堆調整則larger的值等于左節點或者右節點的，這個時候做對調值操作
    heap[larger],heap[root] = heap[root],heap[larger]
    MAX_Heapify(heap, HeapSize, larger)
def Build_MAX_Heap(heap):#構造一個堆，將堆中所有數據重新排序
  HeapSize = len(heap)#將堆的長度當獨拿出來方便
  for i in xrange((HeapSize -2)//2,-1,-1):#從后往前出數
    MAX_Heapify(heap,HeapSize,i)
def HeapSort(heap):#將根節點取出與最后一位做對調，對前面len-1個節點繼續進行對調整過程。
  Build_MAX_Heap(heap)
  for i in range(len(heap)-1,-1,-1):
    heap[0],heap[i] = heap[i],heap[0]
    MAX_Heapify(heap, i, 0)
  return heap
if __name__ == '__main__':
  a = [30,50,57,77,62,78,94,80,84]
  print a
  HeapSort(a)
  print a
  b = [random.randint(1,1000) for i in range(1000)]
  print b
  HeapSort(b)
  print b

運行結果：

[30, 50, 57, 77, 62, 78, 94, 80, 84]
[30, 50, 57, 62, 77, 78, 80, 84, 94]
[107, 115, 207, 919, 128, 651, 534, 546, 217, 295, 54, 202, 498, 620, 174, 897, 873, 112, 873, 729, 588, 669, 994, 773, 462, 550, 347, 597, 440, 426, 271, 677, 323, 302, 604, 154, 589, 871, 235, 305, 502, 743, 575, 53, 130, 686, 726, 959, 980, 884, 542, 246, 292, 226, 608, 357, 229, 168, 415, 671, 972, 142, 472, 375, 522, 486, 241, 368, 839, 841, 137, 545, 427, 601, 476, 229, 757, 601, 136, 506, 394, 975, 162, 163, 26, 776, 886, 82, 37, 248, 47, 246, 23, 895, 623, 373, 147, 109, 553, 176, 204, 530, 927, 656, 153, 487, 743, 113, 20, 334, 554, 850, 510, 423, 373, 207, 795, 403, 499, 509, 531, 256, 920, 313, 694, 322, 100, 825, 578, 954, 526, 92, 820, 9, 931, 303, 408, 132, 833, 194, 902, 766, 14, 140, 729, 328, 636, 316, 536, 232, 687, 425, 811, 432, 955, 715, 339, 861, 736, 411, 901, 609, 353, 97, 330, 896, 852, 1000, 828, 5, 879, 41, 642, 719, 35, 621, 742, 285, 715, 987, 246, 641, 636, 993, 368, 140, 319, 647, 555, 436, 479, 85, 669, 899, 556, 71, 237, 189, 211, 106, 623, 164, 371, 137, 730, 679, 491, 981, 372, 483, 50, 676, 125, 868, 903, 33, 555, 710, 199, 835, 458, 311, 384, 81, 784, 338, 3, 665, 934, 362, 122, 816, 2, 439, 869, 94, 806, 760, 309, 372, 360, 61, 756, 995, 642, 652, 176, 85, 735, 894, 745, 654, 734, 699, 933, 59, 168, 311, 313, 758, 753, 122, 195, 902, 527, 305, 106, 281, 321, 681, 323, 858, 877, 278, 966, 706, 947, 648, 893, 247, 882, 931, 859, 675, 243, 129, 424, 475, 478, 946, 720, 881, 737, 470, 252, 921, 382, 659, 441, 854, 553, 134, 116, 183, 285, 353, 285, 840, 80, 661, 353, 556, 916, 861, 901, 496, 888, 686, 70, 600, 998, 457, 707, 980, 572, 950, 111, 3, 320, 620, 181, 796, 731, 892, 629, 106, 539, 58, 173, 126, 922, 381, 129, 859, 63, 633, 723, 628, 661, 128, 582, 893, 479, 379, 831, 863, 245, 49, 735, 419, 713, 887, 833, 399, 26, 698, 280, 839, 220, 604, 764, 782, 974, 912, 939, 604, 26, 229, 130, 949, 99, 671, 481, 885, 907, 116, 621, 546, 201, 21, 213, 242, 172, 899, 627, 996, 933, 957, 168, 386, 788, 643, 200, 646, 32, 496, 722, 375, 271, 553, 542, 370, 904, 393, 74, 42, 948, 428, 155, 311, 486, 708, 936, 819, 201, 763, 927, 596, 26, 902, 467, 31, 631, 540, 472, 909, 809, 832, 88, 240, 934, 598, 531, 337, 839, 552, 183, 694, 611, 693, 518, 397, 897, 526, 849, 15, 776, 438, 133, 771, 412, 174, 619, 245, 711, 423, 383, 556, 604, 310, 139, 879, 995, 870, 173, 98, 174, 441, 627, 712, 637, 470, 350, 509, 261, 648, 443, 152, 690, 486, 901, 52, 425, 45, 684, 243, 94, 655, 679, 534, 31, 778, 405, 316, 8, 640, 236, 903, 526, 579, 43, 595, 884, 225, 188, 483, 909, 890, 846, 794, 682, 649, 569, 1000, 840, 292, 614, 986, 305, 800, 763, 563, 266, 134, 202, 156, 231, 896, 174, 696, 914, 235, 302, 358, 538, 595, 770, 462, 13, 960, 768, 106, 119, 370, 602, 807, 622, 770, 359, 768, 209, 314, 195, 590, 527, 275, 775, 785, 271, 557, 680, 756, 399, 426, 730, 57, 905, 643, 852, 406, 932, 204, 757, 348, 655, 812, 891, 887, 214, 171, 296, 279, 81, 383, 668, 271, 335, 345, 541, 997, 659, 671, 732, 525, 811, 612, 704, 23, 1000, 511, 731, 505, 818, 815, 766, 689, 978, 721, 987, 546, 824, 753, 277, 838, 16, 382, 910, 332, 301, 727, 851, 395, 310, 649, 432, 864, 894, 756, 400, 116, 31, 990, 232, 611, 75, 969, 600, 823, 58, 236, 378, 489, 222, 269, 382, 745, 984, 278, 530, 994, 493, 182, 681, 822, 664, 241, 126, 502, 167, 546, 710, 956, 647, 454, 776, 525, 46, 537, 550, 374, 497, 787, 577, 540, 538, 552, 187, 862, 392, 266, 269, 885, 563, 430, 13, 853, 936, 566, 366, 236, 962, 877, 15, 812, 231, 929, 123, 484, 331, 237, 310, 835, 643, 55, 85, 345, 341, 86, 742, 852, 309, 489, 414, 295, 288, 464, 513, 573, 322, 785, 697, 988, 425, 376, 677, 56, 833, 482, 61, 611, 701, 709, 420, 682, 74, 690, 800, 962, 828, 722, 194, 524, 692, 516, 576, 854, 942, 682, 265, 710, 826, 648, 769, 843, 424, 387, 91, 256, 352, 378, 649, 660, 479, 208, 75, 570, 394, 372, 736, 701, 464, 430, 704, 395, 425, 377, 724, 349, 204, 281, 317, 711, 337, 953, 599, 615, 93, 395, 926, 78, 447, 649, 893, 928, 63, 763, 978, 920, 426, 370, 524, 312, 820, 885, 667, 298, 18, 170, 657, 698, 483, 532, 891, 486, 263, 480, 648, 898, 923, 288, 51, 786, 733, 782, 116, 471, 440, 703, 600, 983, 479, 19, 983, 145, 88, 781, 899, 565, 258, 862, 374, 4, 634, 560, 691, 875, 735, 622, 646, 291, 782, 562, 249, 640, 263, 62, 638, 510, 237, 653, 990, 926, 805, 717, 32, 513, 502, 217, 273, 905, 266, 554, 922, 950, 538, 322, 347, 230, 687, 359, 452, 360, 211, 755, 44, 898, 611, 431, 610, 450, 526, 771, 933, 179, 132, 326, 884, 966, 870, 957, 523, 381, 917, 368, 845, 714, 588, 357, 230, 436, 924, 865, 341, 139, 239, 971, 433, 452, 794, 737, 814, 368, 655, 442, 870, 691, 564, 384, 480, 235, 322, 485, 867, 404, 597, 955, 83, 432, 352, 183, 45, 486, 210, 270, 264, 213, 722, 283, 582, 1, 521, 804, 846, 261, 540, 494, 260, 168, 758, 873, 543, 409, 313, 397, 386, 730, 692, 420, 299, 26, 489, 838, 278, 415, 376, 896, 416, 936, 569, 945, 485, 672, 969, 997, 929, 981, 582, 59, 534, 547]
[1, 2, 3, 3, 4, 5, 8, 9, 13, 13, 14, 15, 15, 16, 18, 19, 20, 21, 23, 23, 26, 26, 26, 26, 26, 31, 31, 31, 32, 32, 33, 35, 37, 41, 42, 43, 44, 45, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 58, 59, 59, 61, 61, 62, 63, 63, 70, 71, 74, 74, 75, 75, 78, 80, 81, 81, 82, 83, 85, 85, 85, 86, 88, 88, 91, 92, 93, 94, 94, 97, 98, 99, 100, 106, 106, 106, 106, 107, 109, 111, 112, 113, 115, 116, 116, 116, 116, 119, 122, 122, 123, 125, 126, 126, 128, 128, 129, 129, 130, 130, 132, 132, 133, 134, 134, 136, 137, 137, 139, 139, 140, 140, 142, 145, 147, 152, 153, 154, 155, 156, 162, 163, 164, 167, 168, 168, 168, 168, 170, 171, 172, 173, 173, 174, 174, 174, 174, 176, 176, 179, 181, 182, 183, 183, 183, 187, 188, 189, 194, 194, 195, 195, 199, 200, 201, 201, 202, 202, 204, 204, 204, 207, 207, 208, 209, 210, 211, 211, 213, 213, 214, 217, 217, 220, 222, 225, 226, 229, 229, 229, 230, 230, 231, 231, 232, 232, 235, 235, 235, 236, 236, 236, 237, 237, 237, 239, 240, 241, 241, 242, 243, 243, 245, 245, 246, 246, 246, 247, 248, 249, 252, 256, 256, 258, 260, 261, 261, 263, 263, 264, 265, 266, 266, 266, 269, 269, 270, 271, 271, 271, 271, 273, 275, 277, 278, 278, 278, 279, 280, 281, 281, 283, 285, 285, 285, 288, 288, 291, 292, 292, 295, 295, 296, 298, 299, 301, 302, 302, 303, 305, 305, 305, 309, 309, 310, 310, 310, 311, 311, 311, 312, 313, 313, 313, 314, 316, 316, 317, 319, 320, 321, 322, 322, 322, 322, 323, 323, 326, 328, 330, 331, 332, 334, 335, 337, 337, 338, 339, 341, 341, 345, 345, 347, 347, 348, 349, 350, 352, 352, 353, 353, 353, 357, 357, 358, 359, 359, 360, 360, 362, 366, 368, 368, 368, 368, 370, 370, 370, 371, 372, 372, 372, 373, 373, 374, 374, 375, 375, 376, 376, 377, 378, 378, 379, 381, 381, 382, 382, 382, 383, 383, 384, 384, 386, 386, 387, 392, 393, 394, 394, 395, 395, 395, 397, 397, 399, 399, 400, 403, 404, 405, 406, 408, 409, 411, 412, 414, 415, 415, 416, 419, 420, 420, 423, 423, 424, 424, 425, 425, 425, 425, 426, 426, 426, 427, 428, 430, 430, 431, 432, 432, 432, 433, 436, 436, 438, 439, 440, 440, 441, 441, 442, 443, 447, 450, 452, 452, 454, 457, 458, 462, 462, 464, 464, 467, 470, 470, 471, 472, 472, 475, 476, 478, 479, 479, 479, 479, 480, 480, 481, 482, 483, 483, 483, 484, 485, 485, 486, 486, 486, 486, 486, 487, 489, 489, 489, 491, 493, 494, 496, 496, 497, 498, 499, 502, 502, 502, 505, 506, 509, 509, 510, 510, 511, 513, 513, 516, 518, 521, 522, 523, 524, 524, 525, 525, 526, 526, 526, 526, 527, 527, 530, 530, 531, 531, 532, 534, 534, 534, 536, 537, 538, 538, 538, 539, 540, 540, 540, 541, 542, 542, 543, 545, 546, 546, 546, 546, 547, 550, 550, 552, 552, 553, 553, 553, 554, 554, 555, 555, 556, 556, 556, 557, 560, 562, 563, 563, 564, 565, 566, 569, 569, 570, 572, 573, 575, 576, 577, 578, 579, 582, 582, 582, 588, 588, 589, 590, 595, 595, 596, 597, 597, 598, 599, 600, 600, 600, 601, 601, 602, 604, 604, 604, 604, 608, 609, 610, 611, 611, 611, 611, 612, 614, 615, 619, 620, 620, 621, 621, 622, 622, 623, 623, 627, 627, 628, 629, 631, 633, 634, 636, 636, 637, 638, 640, 640, 641, 642, 642, 643, 643, 643, 646, 646, 647, 647, 648, 648, 648, 648, 649, 649, 649, 649, 651, 652, 653, 654, 655, 655, 655, 656, 657, 659, 659, 660, 661, 661, 664, 665, 667, 668, 669, 669, 671, 671, 671, 672, 675, 676, 677, 677, 679, 679, 680, 681, 681, 682, 682, 682, 684, 686, 686, 687, 687, 689, 690, 690, 691, 691, 692, 692, 693, 694, 694, 696, 697, 698, 698, 699, 701, 701, 703, 704, 704, 706, 707, 708, 709, 710, 710, 710, 711, 711, 712, 713, 714, 715, 715, 717, 719, 720, 721, 722, 722, 722, 723, 724, 726, 727, 729, 729, 730, 730, 730, 731, 731, 732, 733, 734, 735, 735, 735, 736, 736, 737, 737, 742, 742, 743, 743, 745, 745, 753, 753, 755, 756, 756, 756, 757, 757, 758, 758, 760, 763, 763, 763, 764, 766, 766, 768, 768, 769, 770, 770, 771, 771, 773, 775, 776, 776, 776, 778, 781, 782, 782, 782, 784, 785, 785, 786, 787, 788, 794, 794, 795, 796, 800, 800, 804, 805, 806, 807, 809, 811, 811, 812, 812, 814, 815, 816, 818, 819, 820, 820, 822, 823, 824, 825, 826, 828, 828, 831, 832, 833, 833, 833, 835, 835, 838, 838, 839, 839, 839, 840, 840, 841, 843, 845, 846, 846, 849, 850, 851, 852, 852, 852, 853, 854, 854, 858, 859, 859, 861, 861, 862, 862, 863, 864, 865, 867, 868, 869, 870, 870, 870, 871, 873, 873, 873, 875, 877, 877, 879, 879, 881, 882, 884, 884, 884, 885, 885, 885, 886, 887, 887, 888, 890, 891, 891, 892, 893, 893, 893, 894, 894, 895, 896, 896, 896, 897, 897, 898, 898, 899, 899, 899, 901, 901, 901, 902, 902, 902, 903, 903, 904, 905, 905, 907, 909, 909, 910, 912, 914, 916, 917, 919, 920, 920, 921, 922, 922, 923, 924, 926, 926, 927, 927, 928, 929, 929, 931, 931, 932, 933, 933, 933, 934, 934, 936, 936, 936, 939, 942, 945, 946, 947, 948, 949, 950, 950, 953, 954, 955, 955, 956, 957, 957, 959, 960, 962, 962, 966, 966, 969, 969, 971, 972, 974, 975, 978, 978, 980, 980, 981, 981, 983, 983, 984, 986, 987, 987, 988, 990, 990, 993, 994, 994, 995, 995, 996, 997, 997, 998, 1000, 1000, 1000]

這里的函數名我就直接用了wiki上對堆操作的定義，方便理解，其實也是方便我以后來看。

時間復雜度

堆排序的時間復雜度分為兩個部分一個是建堆的時候所耗費的時間，一個是進行堆調整的時候所耗費的時間。而堆排序則是調用了建堆和堆調整。

剛剛在上面也提及到了，建堆是一個線性過程，從len/2-0一直調用堆調整的過程，相當于o(h2)+o(h3)+…+o(hlen/2)這里的h表示節點深度，len/2表示節點深度，對于求和過程，結果為線性的O（n）

堆調整為一個遞歸的過程，調整堆的過程時間復雜度與堆的深度有關系，相當于lgn的操作。

因為建堆的時間復雜度是O（n）,調整堆的時間復雜度是lgn，所以堆排序的時間復雜度是O（nlgn）。

PS：這里再為大家推薦一款關于排序的演示工具供大家參考：

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python列表(list)操作技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》

希望本文所述對大家Python程序設計有所幫助。