힙정렬 구현

1 C[ | ]

#include<stdio.h>
void heap_heapify(int a[], int size, int i) {
	int temp, left=2*i+1, right=2*i+2, largest=i;
	if( left<size && a[left]>a[largest] ) largest=left;
	if( right<size && a[right]>a[largest] ) largest=right;
	if( largest == i ) return;
	temp=a[i]; a[i]=a[largest]; a[largest]=temp;
	heap_heapify(a, size, largest);
}
void heap_sort(int a[], int size) {
	for(int i=size/2-1; i>=0; i--) heap_heapify(a, size, i);
	int temp;
	for(int i=size-1; i>=0; i--) {
		temp=a[0]; a[0]=a[i]; a[i]=temp;
		heap_heapify(a, i, 0);
	}
}
int main() {
	int arr[] = {9,1,22,4,0,-1,1,22,100,10};
	int size = sizeof(arr)/sizeof(int);
	heap_sort(arr, size);
	for(int i=0; i<size; i++) printf("%d ", arr[i]);
	// -1 0 1 1 4 9 10 22 22 100 
}

2 C++[ | ]

C++ 힙정렬 구현 문서를 참고하십시오.

#include <iostream>
void heap_heapify(int a[], int size, int i) {
	int left=2*i+1, right=2*i+2, largest=i;
	if( left<size && a[left]>a[largest] ) largest=left;
	if( right<size && a[right]>a[largest] ) largest=right;
	if( largest == i ) return;
	std::swap(a[i], a[largest]);
	heap_heapify(a, size, largest);
}
void heap_sort(int a[], int size) {
	for(int i=size/2-1; i>=0; i--) heap_heapify(a, size, i);
	for(int i=size-1; i>=0; i--) {
		std::swap(a[0], a[i]);
		heap_heapify(a, i, 0);
	}
}
int main() {
	int arr[] = {9,1,22,4,0,-1,1,22,100,10};
	heap_sort(arr, sizeof(arr)/sizeof(int));
	for(int x: arr) std::cout << x << " ";
	// -1 0 1 1 4 9 10 22 22 100 
}

3 C#[ | ]

C샵 힙정렬 구현 문서를 참고하십시오.

using System;
class Program {
    static void heapSort(int[] arr) {
        int i, temp, length = arr.Length;
        for(i=length/2-1; i>=0; i--) heapHeapify(arr, length, i);
        for(i=length-1; i>=0; i--) {
            temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
            heapHeapify(arr, i, 0);
        }
    }
    static void heapHeapify(int[] arr, int length, int i) {
        int left = 2*i + 1, right = 2*i + 2;
        int temp, largest = i;
        if( left<length && arr[left]>arr[largest]) largest = left;
        if( right<length && arr[right]>arr[largest]) largest = right;
        if( largest != i ) {
            temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
            heapHeapify(arr, length, largest);
        }
    }
    static void Main() {
        int[] arr = {9,1,22,4,0,-1,1,22,100,10};
        heapSort(arr);
        Console.Write(string.Join(",",arr));
        // -1,0,1,1,4,9,10,22,22,100
    }
}

4 Java[ | ]

Java 힙정렬 구현 문서를 참고하십시오.

public class MyClass {
    private static void heapify(int arr[], int length, int i) {
        int left = 2*i + 1, right = 2*i + 2;
        int temp, largest = i;
        if( left<length && arr[left]>arr[largest]) largest = left;
        if( right<length && arr[right]>arr[largest]) largest = right;
        if( largest != i ) {
            temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
            heapify(arr, length, largest);
        }
    }
    private static void heapSort(int arr[]) {
        int i, temp, length = arr.length;
        for(i=length/2-1; i>=0; i--) heapify(arr, length, i);
        for(i=length-1; i>=0; i--) {
            temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void main(String args[]) {
        int arr[] = {9,1,22,4,0,-1,1,22,100,10};
        heapSort(arr);
        for(int x: arr) System.out.format("%d ",x);
        // -1 0 1 1 4 9 10 22 22 100 
    }
}

5 PHP[ | ]

PHP 힙정렬 구현 문서를 참고하십시오.

<?php
function heap_sort(&$a) {
    $heapify = function(&$a, $size, $i) use (&$heapify) {
        $largest = $i;
        $L = 2*$i + 1;
        $R = 2*$i + 2;
        if( $L<$size && $a[$i]<$a[$L] ) $largest=$L;
        if( $R<$size && $a[$largest]<$a[$R] ) $largest=$R;
        if( $largest != $i ) {
        	$temp=$a[$i]; $a[$i]=$a[$largest]; $a[$largest]=$temp;
        	$heapify($a, $size, $largest);
        }
    };
    $size = count($a);
    for($i=$size; $i>-1; $i--) $heapify($a, $size, $i);
    for($i=$size-1; $i>0; $i--) {
        $temp=$a[$i]; $a[$i]=$a[0]; $a[0]=$temp;
        $heapify($a, $i, 0);
    }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
heap_sort( $arr );
echo implode(',',$arr);
# -1,0,1,1,4,9,10,22,22,100

6 Python[ | ]

Python 힙정렬 구현 문서를 참고하십시오.

def heap_sort(a):
    def heapify(a, size, i):
    	largest = i
    	L = 2*i + 1
    	R = 2*i + 2
    	if L<size and a[i]<a[L]: largest=L
    	if R<size and a[largest]<a[R]: largest=R
    	if largest != i:
    		a[i], a[largest] = a[largest], a[i]
    		heapify(a, size, largest)
    size = len(a)
    for i in range(size, -1, -1): heapify(a, size, i)
    for i in range(size-1, 0, -1):
    	a[i], a[0] = a[0], a[i]
    	heapify(a, i, 0)
arr = [9,1,22,4,0,-1,1,22,100,10]
heap_sort(arr)
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

7 Ruby[ | ]

Ruby 힙정렬 구현 문서를 참고하십시오.

def heap_sort(a)
    def heapify(a, size, i)
    	largest = i
    	l = 2*i + 1
    	r = 2*i + 2
    	if l<size and a[i]<a[l]; largest=l; end
    	if r<size and a[largest]<a[r]; largest=r; end
    	if largest != i
    		a[i],a[largest] = a[largest],a[i]
    		heapify(a, size, largest)
    	end
    end
    for i in (a.size).downto(0); heapify(a, a.size, i); end
    for i in (a.size-1).downto(1)
    	a[i],a[0] = a[0],a[i]
    	heapify(a, i, 0)
    end
end
arr = [9,1,22,4,0,-1,1,22,100,10]
heap_sort(arr)
print arr
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

8 같이 보기[ | ]

9 참고[ | ]

https://www.geeksforgeeks.org/heap-sort/