function buildMaxHeap(arr){// 建立大頂堆 len = arr.length; for(var i =Math.floor(len/2); i >=0; i--){ heapify(arr, i); } }
function heapify(arr, i){// 堆調整 var left =2* i +1, right =2* i +2, largest = i;
if(left < len && arr[left]> arr[largest]){ largest = left; }
if(right < len && arr[right]> arr[largest]){ largest = right; }
if(largest != i){ swap(arr, i, largest); heapify(arr, largest); } }
function swap(arr, i, j){ var temp = arr[i]; arr[i]= arr[j]; arr[j]= temp; }
function heapSort(arr){ buildMaxHeap(arr);
for(var i = arr.length-1; i >0; i--){ swap(arr,0, i); len--; heapify(arr,0); } return arr; }
Python
實例
def buildMaxHeap(arr): importmath for i inrange(math.floor(len(arr)/2),-1,-1): heapify(arr,i)
def heapify(arr, i): left =2*i+1 right =2*i+2 largest = i if left < arrLen and arr[left]> arr[largest]: largest = left if right < arrLen and arr[right]> arr[largest]: largest = right
if largest != i: swap(arr, i, largest) heapify(arr, largest)
def swap(arr, i, j): arr[i], arr[j]= arr[j], arr[i]
def heapSort(arr): global arrLen arrLen =len(arr) buildMaxHeap(arr) for i inrange(len(arr)-1,0,-1): swap(arr,0,i) arrLen -=1 heapify(arr,0) return arr
func heapify(arr []int,i, arrLen int){ left :=2*i+1 right :=2*i+2 largest :=i if left < arrLen && arr[left] > arr[largest]{ largest = left } if right < arrLen && arr[right] > arr[largest]{ largest = right } if largest !=i{ swap(arr,i, largest) heapify(arr, largest, arrLen) } }
void max_heapify(int arr[],int start,int end){ // 建立父節點指標和子節點指標 int dad = start; int son = dad *2+1; while(son <= end){// 若子節點指標在範圍內才做比較 if(son +1<= end && arr[son]< arr[son +1])// 先比較兩個子節點大小,選擇最大的 son++; if(arr[dad]> arr[son])//如果父節點大於子節點代表調整完畢,直接跳出函數 return; else{// 否則交換父子內容再繼續子節點和孫節點比較 swap(&arr[dad],&arr[son]); dad = son; son = dad *2+1; } } }
void heap_sort(int arr[],int len){ int i; // 初始化,i從最後一個父節點開始調整 for(i = len /2-1; i >=0; i--) max_heapify(arr, i, len -1); // 先將第一個元素和已排好元素前一位做交換,再重新調整,直到排序完畢 for(i = len -1; i >0; i--){ swap(&arr[0],&arr[i]); max_heapify(arr,0, i -1); } }
int main(){ int arr[]={3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6}; int len =(int)sizeof(arr)/sizeof(*arr); heap_sort(arr, len); int i; for(i =0; i < len; i++) printf("%d ", arr[i]); printf(""); return0; }
void max_heapify(int arr[], int start, int end){ // 建立父節點指標和子節點指標 int dad = start; int son = dad *2+1; while(son <= end){// 若子節點指標在範圍內才做比較 if(son +1<= end && arr[son]< arr[son +1])// 先比較兩個子節點大小,選擇最大的 son++; if(arr[dad]> arr[son])// 如果父節點大於子節點代表調整完畢,直接跳出函數 return; else{// 否則交換父子內容再繼續子節點和孫節點比較 swap(arr[dad], arr[son]); dad = son; son = dad *2+1; } } }
void heap_sort(int arr[], int len){ // 初始化,i從最後一個父節點開始調整 for(int i = len /2-1; i >=0; i--) max_heapify(arr, i, len -1); // 先將第一個元素和已經排好的元素前一位做交換,再從新調整(剛調整的元素之前的元素),直到排序完畢 for(int i = len -1; i >0; i--){ swap(arr[0], arr[i]); max_heapify(arr, 0, i -1); } }
int main(){ int arr[]={3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6}; int len =(int)sizeof(arr)/sizeof(*arr); heap_sort(arr, len); for(int i =0; i < len; i++) cout<< arr[i]<<' '; cout<< endl; return0; }