Hello, Stranger

Heap Sort (isnert & remove) 본문

Programming/C/C++

Heap Sort (isnert & remove)

blackcon 2013.11.26 00:03

#include <stdio.h>

#include <iostream>

using namespace std;


void out(int *a)

{

printf("%d\n", a[0]);

for(int i = 0; i < 10;i++){

for(int j = 0; j < 10; j++){

if((2*j+1) == i) printf("%d, %d\n", a[i], i); /*왼쪽 출력*/

else if((2*j+2) == i) printf("%d, %d\n\n", a[i], i); /*오른쪽 출력*/

}

}

}


void insert(int *a, int data)

{

/*

1. 마지막(현재) 인덱스에 data를 넣는다.

2. 부모와 비교하면서 자식이 크면 자리를 바꾼다.

*/

int current =10;

int parent = 0;

int tmp = 0;

a[current] = data;

parent = (current -1)/2;


while((current != 0) && (a[current] > a[parent])){

tmp = a[parent];

a[parent] = a[current];

a[current] = tmp;

current = parent; /*부모인덱스 변경*/

parent = (current -1) / 2; /*자식으로 설정*/

}

}


void downheap(int *a, int current)

{

int child = 0;

int tmp = 0;

if(current == 10) return;

else{

child = 2 * current + 1;

if(child+1 != 0){

if(a[child+1] > a[child]) child = child +1;

}

if(a[current] < a[child]){

tmp = a[current];

a[current] = a[child];

a[child] = a[current];


downheap(a, child);

}

}

}

void remove(int *a)

{

int cnt = 10;

int data = a[0]; /*root값 return*/

a[0] = a[cnt - 1]; /*마지막값 root로 이동*/

cnt --;

downheap(a, 0);

}

int main(void)

{

int a[10] = {24, 19, 12, 17, 10, 5, 4, 9, 7};


insert(a, 26);

out(a);

remove(a);

out(a);


return 0;

}

저작자 표시
신고

'Programming > C/C++' 카테고리의 다른 글

Winpcap Developer 초기 설정  (0) 2015.07.16
[인공지능] A* 알고리즘을 이용한 8-puzzle 만들기  (6) 2015.04.04
Heap Sort (isnert & remove)  (0) 2013.11.26
string::getline  (0) 2010.11.19
string을 char로 취급하기  (0) 2010.10.21
[펌]private, proteted, public 의 차이  (2) 2010.10.12
0 Comments
댓글쓰기 폼