이 진 로 루틴
이 진 더미 의 ADT 작업 은 주로 Insert (삽입) 와 DeleteMin (최소 원 삭제) 을 포함한다.
1. 구조 적 성질: 더 미 는 완전 이 진 트 리 (이 진 트 리 의 깊이 가 h 이면 h 층 을 제외 하고 다른 각 층 (1 ～ h - 1) 이 모두 채 워 지고 h 층 의 모든 결점 은 맨 왼쪽 에 연속 으로 집중 된다) 로 다음 과 같다.
(1) 완전 이 진 트 리 는 규칙 적 이기 때문에 하나의 배열 로 포인터 로 저장 하지 않 고 다음 과 같은 형식 으로 저장 할 수 있 습 니 다. 그 중에서 [0] 주소 의 요 소 는 흔히 태그 (최소 이 진 트 리 에 있어 아주 작은 값 을 저장 합 니 다) 에 사 용 됩 니 다. 이것 은 프로 그래 밍 이 편리 하기 위해 서 입 니 다. 물론 이 표 시 를 사용 하지 않 아 도 됩 니 다.
(2) 배열 의 임 의 위치 i 에 있 는 요소 에 대해 왼쪽 아들 은 위치 2 * i 에 있 고 오른쪽 아들 은 2 * i + 1 에 있다.이 메 시 지 는 매우 유용 하 다. 그래서 우 리 는 지침 없 이 배열 만으로 좌우 아들 을 편리 하 게 방문 할 수 있다.
2. 쌓 기 순서 성:
우 리 는 최소 원 을 빨리 찾 고 싶 기 때문에 최소 원 은 뿌리 에 있어 야 한다.우 리 는 O (1) 시간 으로 최소 치 를 찾 을 수 있다.
쌓 기 순서 성 이란 한 더미 에서 모든 노드 X, X 아버지 중의 키 워드 는 X 중의 키 워드 를 제외 하고 뿌리 노드 는 제외 합 니 다 (아버지 가 없 기 때 문 입 니 다).
3. 삽입
하나의 요소 X 를 더미 에 삽입 하기 위해 서, 우 리 는 다음 사용 가능 한 위치 에 빈 구멍 을 만 듭 니 다. 그렇지 않 으 면 이 더 미 는 완전 수가 아 닙 니 다.X 가 쌓 인 순 서 를 파괴 하지 않 고 이 구멍 에 넣 을 수 있다 면 삽입 이 완료 되 었 습 니 다.그렇지 않 으 면 우 리 는 구멍 의 아버지 노드 에 있 는 요 소 를 이 구멍 에 옮 겨 넣 으 면 구멍 은 뿌리 방향 으로 한 걸음 씩 나온다.X 가 구멍 에 들 어 갈 때 까지 과정 을 계속 바 꾸 세 요.
이러한 일반적인 전략 을 필터 (percolate up) 라 고 한다.새 원 소 는 정확 한 위 치 를 찾 을 때 까지 쌓 아 올 렸 다.
4. 최소 원 삭제
최소 원 을 삭제 할 때 뿌리 노드 에 구멍 을 만들어 야 합 니 다.현재 원 소 를 하나 덜 쌓 았 기 때문에, 더미 의 마지막 원소 X 는 이 더미 의 어 딘 가로 이동 해 야 한다.X 가 바로 구멍 에 들 어 갈 수 있다 면 deleteMin 이 완성 합 니 다.그러나 이 는 일반적으로 불가능 하기 때문에 우 리 는 빈 구멍 의 두 아들 중 비교적 작은 사람 을 빈 구멍 으로 옮 겨 빈 구멍 을 아래로 한 층 밀 었 다.X 가 빈 구멍 에 들 어 갈 때 까지 이 절 차 를 반복 합 니 다.따라서 우리 의 방법 은 X 를 뿌리 부터 막내 아들 을 포함 하 는 경로 에 올 바른 위치 에 두 는 것 이다.
이런 일반적인 전략 을 하 여과 (percolate down) 라 고 한다.
5. 프로그램 코드 인 스 턴 스
BinHeap. h (types. h 에 서 는 재 정의 일 뿐)
/*
* =====================================================================================
*
* Filename: BinHeap.h
*
* Description:
*
* Version: 1.0
* Created: 2012/12/2 19:20:45
* Revision: none
* Compiler: gcc
*
* Author: xhzuoxin (QQ:1126804077), [email protected]
* Organization:
*
* =====================================================================================
*/
#ifndef _BINHEAP_H
#define _BINHEAP_H
#include "../types.h"
typedef UINT16 EleType;
typedef struct HeapStruct
{
int cur;
int size;
EleType *ele;
}Heap;
typedef Heap* PtrHeap;
typedef UINT16 Position;
/* functions */
extern PtrHeap InitHeap(PtrHeap h, int max_ele);
extern PtrHeap InsertHeap(PtrHeap h, EleType x);
extern EleType DelMinHeap(PtrHeap h);
extern PtrHeap BuildHeap(EleType *x, int n);
extern PtrHeap DecreaseKey(Position pos, int delta, PtrHeap h);
extern PtrHeap IncreaseKey(Position pos, int delta, PtrHeap h);
extern EleType Delete(Position pos, PtrHeap h);
#endif
BinHeap.c
/*
* =====================================================================================
*
* Filename: BinHeap.c
*
* Description:
*
* Version: 1.0
* Created: 2012/12/2 20:17:44
* Revision: none
* Compiler: gcc
*
* Author: xhzuoxin (QQ:1126804077), [email protected]
* Organization:
*
* =====================================================================================
*/
#include
#include
#include "BinHeap.h"
#define ERR_MSG(x) printf(x)
#define MIN_DATA (0)
/*
* === FUNCTION ======================================================================
* Name: PercolateDown
* Description:
* =====================================================================================
*/
static void PercolateDown(PtrHeap h, UINT16 hole)
{
UINT16 i = 0;
UINT16 child = 0;
EleType temp = 0;
if(NULL == h)
{
return;
}
temp = h->ele[hole];
i = hole;
child = 2 * i;
while(child <= h->cur)
{
if(child != h->cur) // have left+right child
{
if(h->ele[child+1] < h->ele[child])
{
child = child + 1;
}
}
// compare to h->ele[hole]
if(temp > h->ele[child])
{
h->ele[i] = h->ele[child];
}
else
{
break;
}
i = child;
child = 2 * i;
}
h->ele[i] = temp;
}
/*
* === FUNCTION ======================================================================
* Name: PercolateUp
* Description:
* =====================================================================================
*/
static void PercolateUp(PtrHeap h, UINT16 hole)
{
EleType temp = h->ele[hole];
UINT16 i = 0;
UINT16 parent = 0;
i = hole;
parent = i >> 1;
while(temp < h->ele[parent])
{
h->ele[i] = h->ele[parent];
i = parent;
parent = i >> 1;
}
h->ele[i] = temp;
}
/*
* === FUNCTION ======================================================================
* Name: InitHeap
* Description:
* =====================================================================================
*/
PtrHeap InitHeap(PtrHeap h, int max_ele)
{
if(h != NULL)
{
if(h->ele != NULL)
{
free(h->ele);
}
free(h);
}
h = (PtrHeap)malloc(sizeof(Heap));
if(NULL == h)
{
ERR_MSG("out of space!
");
return NULL;
}
h->ele = (EleType *)malloc(max_ele*sizeof(EleType));
if(NULL == h->ele)
{
ERR_MSG("out of space!
");
return NULL;
}
h->size = max_ele;
h->cur = 0;
h->ele[0] = MIN_DATA;
return h;
}
/*
* === FUNCTION ======================================================================
* Name: InsertHeap
* Description: insert is a percolate up operator
* =====================================================================================
*/
PtrHeap InsertHeap(PtrHeap h, EleType x)
{
int i = 0;
if(h->cur >= h->size-1)
{
ERR_MSG("Heap is full!
");
return NULL;
}
for(i = ++h->cur; h->ele[i>>1] > x; i >>= 1)
{
h->ele[i] = h->ele[i>>1];
}
h->ele[i] = x;
return h;
}
/*
* === FUNCTION ======================================================================
* Name: DelMinHeap
* Description:
* =====================================================================================
*/
EleType DelMinHeap(PtrHeap h)
{
int i = 0;
int child = 0;
EleType min_ele, last_ele;
if(h->cur == 0) /* empty heap */
{
ERR_MSG("Heap is empty!
");
return h->ele[0];
}
min_ele = h->ele[1];
last_ele = h->ele[h->cur];
h->cur--;
i = 1;
child = 2 * i;
while(child <= h->cur)
{
if((child < h->cur) && (h->ele[child+1] < h->ele[child]))
{
child++;
}
/* compare to last_element */
if(h->ele[child] < last_ele)
{
h->ele[i] = h->ele[child];
}
else
{
break;
}
i = child;
child = 2 * i;
}
h->ele[i] = last_ele;
return min_ele;
}
/*
* === FUNCTION ======================================================================
* Name: BuildHeap
* Description:
* =====================================================================================
*/
PtrHeap BuildHeap(EleType *x, int n)
{
PtrHeap h = NULL;
int i = 0;
h = InitHeap(h, n*2); /* include ele[0]=0 */
for(i=0; iele[i+1] = x[i];
}
h->cur = n;
for(i=n/2; i>0; i--)
{
PercolateDown(h, i);
}
return h;
}
/*
* === FUNCTION ======================================================================
* Name: IncreaseKey
* Description:
* pos --
* delta --
* h --
* =====================================================================================
*/
PtrHeap IncreaseKey(Position pos, int delta, PtrHeap h)
{
// increase pos
h->ele[pos] += delta;
PercolateDown(h, pos);
return h; // also needn't this line
}
/*
* === FUNCTION ======================================================================
* Name: DecreaseKey
* Description:
* pos --
* delta --
* h --
* =====================================================================================
*/
PtrHeap DecreaseKey(Position pos, int delta, PtrHeap h)
{
// decrease pos
h->ele[pos] -= delta;
PercolateUp(h, pos);
return h;
}
/*
* === FUNCTION ======================================================================
* Name: Delete
* Description: Delete a element in Heap.
* First, use DecreaseKey(P, Infinite, H);
* Second, use DeleteMin(H)
* =====================================================================================
*/
EleType Delete(Position pos, PtrHeap h)
{
EleType temp = h->ele[pos];
DecreaseKey(pos, h->ele[pos], h); // set ele[POS] want to delete to 0
if(0 != DelMinHeap(h))
{
return 0;
}
return temp;
} TestSuite. c (CUnit 테스트 파일 사용)
/*
* =====================================================================================
*
* Filename: TestSuite.c
*
* Description: test file
*
* Version: 1.0
* Created: 2012/12/3 14:03:34
* Revision: none
* Compiler: gcc
*
* Author: xhzuoxin (QQ:1126804077), [email protected]
* Organization:
*
* =====================================================================================
*/
#include
#include
#include "CUnit/Console.h"
#include "BinHeap.h"
PtrHeap h = NULL;
int InitSuite(void)
{
if(NULL == (h=InitHeap(h, 30)))
{
return -1;
}
else
{
return 0;
}
return 0;
}
int EndSuite(void)
{
free(h->ele);
free(h);
return 0;
}
void TestInsertHeap(void)
{
int i = 0;
if(NULL != h)
{
CU_ASSERT(NULL != InsertHeap(h, 50));
CU_ASSERT(NULL != InsertHeap(h, 100));
CU_ASSERT(NULL != InsertHeap(h, 200));
}
printf("
InsertHeap: ");
for(i=1; i<=h->cur; i++)
{
printf("%d ", h->ele[i]);
}
}
void TestDelMinHeap(void)
{
printf("
DelMin: ");
while(h->cur > 0)
{
printf("%d ", DelMinHeap(h));
}
}
void TestBuildHeap(void)
{
int i = 0;
EleType x[15] = {10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2};
h = BuildHeap(x, 15);
printf("
BuildHeap:");
for(i=1; i<=h->cur; i++)
{
printf("%d ", h->ele[i]);
}
}
void TestIncreaseKey(void)
{
int pos = 5;
int delta = 50;
int i = 0;
h = IncreaseKey(pos, delta, h);
printf("
IncreaseKey:");
for(i=1; i<=h->cur; i++)
{
printf("%d ", h->ele[i]);
}
}
void TestDecreaseKey(void)
{
int pos = 5;
int delta = 1;
int i = 0;
h = DecreaseKey(pos, delta, h);
printf("
DecreaseKey:");
for(i=1; i<=h->cur; i++)
{
printf("%d ", h->ele[i]);
}
}
void TestDelete(void)
{
int pos = 5;
EleType e = Delete(pos, h);
printf("
Delete: %d", e);
}
int main(void)
{
// CU_pSuite suite = NULL;
//
// /* Init registry */
// if(CUE_SUCCESS != CU_initialize_registry())
// {
// return CU_get_error();
// }
//
// /* add suite */
// suite = CU_add_suite("suite1", InitSuite, EndSuite);
// if(NULL == suite)
// {
// CU_cleanup_registry();
// return CU_get_error();
// }
//
// /* add tests */
// if(NULL == CU_add_test(suite, "test of InsertHeap()", TestInsertHeap)
// || NULL == CU_add_test(suite, "test of DelMinHeap()", TestDelMinHeap))
// {
// CU_cleanup_registry();
// return CU_get_error();
// }
//
// /* run */
// CU_console_run_tests();
//
// /* cleanup */
// CU_cleanup_registry();
CU_TestInfo testcase[] = {
{"TestBuild", TestBuildHeap},
{"TestInsert", TestInsertHeap},
{"TestIncreaseKey", TestIncreaseKey},
{"TestDecreaseKey", TestDecreaseKey},
{"TestDelete", TestDelete},
{"TestDelMin", TestDelMinHeap},
CU_TEST_INFO_NULL
};
CU_SuiteInfo suite[] = {
{"Testing func ", InitSuite, EndSuite, testcase},
CU_SUITE_INFO_NULL
};
/* Init registry */
if(CUE_SUCCESS != CU_initialize_registry())
{
return CU_get_error();
}
/* register suite */
if(CUE_SUCCESS != CU_register_suites(suite))
{
return 1;
}
CU_console_run_tests();
CU_cleanup_registry();
return 0;
}
위의 프로그램 에는 인 서 트 와 DeleteMin 작업 뿐만 아니 라 BuildHeap 작업 도 포함 되 어 있다.비록 BuildHeap 는 여러 번 삽입 작업 을 사용 하여 완성 할 수 있 지만 우 리 는 일반적으로 이렇게 하지 않 습 니 다. 일반적으로 여과 하 는 방법 (아래 그림) 을 사용 합 니 다. 상세 한 설명 은 라 는 책 을 참고 할 수 있 습 니 다.트 리 에 N 항목 을 임의의 순서 로 넣 고 구조 적 특성 을 유지 하기 시작 합 니 다.이 때 percolateDown (i) 이 노드 i 에서 거 르 면 buildHeap 프로그램 은 구조 적 방법 으로 순서 가 있 는 나 무 를 만 드 는 데 사용 할 수 있 습 니 다.
그림 6 - 15 의 첫 번 째 나 무 는 무질서 한 나무 이다.그림 6 - 15 부터 그림 6 - 18 까지 나머지 7 그루 의 나 무 는 7 개의 percolateDown 에서 각각 실행 결 과 를 나타 낸다.모든 점선 은 두 번 의 비교 에 대응 합 니 다. 한 번 은 작은 아들 노드 를 찾 는 것 이 고 다른 하 나 는 작은 아들 과 이 노드 의 비교 입 니 다.전체 알고리즘 중 10 번 의 점선 만 있 고 20 번 의 비교 에 대응 합 니 다.
마지막 으로 gcc 로 컴 파일 된 makfile 파일 은
SRC=BinHeap.c BinHeap.h TestSuite.c
LIB=-L/usr/local/lib
INC=-I/usr/local/include
TestSuite:$(SRC)
gcc $^ -o $@ $(LIB) $(INC) -lcunit -g -Wall -static
.PHONY:clean tags
clean:
rm -f TestSuite *~
tags:
ctags -R --c++-kinds=+p --fields=+iaS --extra=+q
테스트 결 과 는 다음 과 같 습 니 다 (정확).
테스트 열 실행 과정:
(1) BuildHeap 을 사용 하여 쌓 기;
(2) 요소 (50, 100, 200) 를 더미 에 삽입 하려 고 시도 합 니 다.
(3) pos = 5 곳 의 키워드 값 증가;
(4) pos = 5 개의 키워드 의 값 을 감소 합 니 다.
(5) Delete 함수 가 pos = 5 곳 의 키워드 값 을 삭제 합 니 다.
(6) 쌓 아 올 릴 때 까지 최소 원 을 하나씩 삭제 합 니 다.
참고:
(1) 의 데이터 구조 와 알고리즘 분석 - C 언어 설명
（2）http://blog.csdn.net/gqltt/article/details/7718484
（3）http://program.sinaapp.com/?p=49컴퓨터 프로 그래 밍 예술 * 알고리즘 교류
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
