「データ構造」優先キュー(Priority Queue)と「heap」hipを実装し、優先キュー(9-2-2)を完了します.

まず、それは良いモデルではありませんが、お尻を理解しやすい方法で実現しました.
もっと合理的な形に変えましょう!
まずタイトルファイルを見てみましょう
SimpleHeap.h

//
//  SimpleHeap.h
//  Heap
//
//  Created by 서희찬 on 2021/04/11.
//

#ifndef SimpleHeap_h
#define SimpleHeap_h

#define TRUE 1
#define FALSE 0

#define HEAP_LEN 100

typedef char HData;
typedef int priority;

typedef struct _heapElem
{
    Priority pr; // 값이 작을수록 높은 우선순위
    HData data;
}HeapElem;

typedef struct _heap
{
    int numOfData;
    HeapElem heapArr[HEAP_LEN];
}Heap;

void HeapInit(Heap * ph);
int HIsEmpty(Heap * ph);

void HInsert(Heap * ph, HData data, Priority pr);
HData HDelete(Heap * ph);

#endif /* SimpleHeap_h */

上のファイルは,純粋なhipを実現するヘッダファイルというより,優先順位キューを実現することを考慮して定義されたヘッダファイルである.
これは構造体定義で感じることができる.
優先度情報を単独で含めることができるprを定義することにより,優先度キューの実装が考慮されていることがわかる.

原理中心のHIP実施：HDelete中心

次に、ヘッダファイルで宣言された関数の定義を表示する前に、次の事実を整理して覚えておく必要があります.

お尻は完全にバイナリツリーです.

hipの実装は配列に基づいており、インデックスが0の要素は空である.

したがって,hipに格納されるノード数は最後のノードの固有番号と一致する.

ノードの固有番号は、ノードストレージアレイのインデックス値となる.

の優先度を表す整数値が小さいほど、優先度が高いと仮定する.

これに基づいてコードを書きます!
SimpleHeap.c

//
//  SimpleHeap.c
//  Heap
//
//  Created by 서희찬 on 2021/04/11.
//

#include "SimpleHeap.h"

void HeapInit(Heap * ph) // 힙의 초기화
{
   ph->numOfData = 0;
}

int HIsEmpty(Heap * ph) // 힙이 비었는지 체크
{
   if(ph->numOfData == 0)
       return TRUE;
   else
       return FALSE;
}

int GetParentIDX(int idx) // 부모 노드의 인덱스 값 반환
{
   return idx/2;
}

int GetLChildIDX(int idx) // 왼쪽 자식 노드의 인덱스 값 반환
{
   return idx*2;
}

int GetRChildIDX(int idx) // 오른쪽 자식 노드의 인덱스 값 반환
{
   return GetLChildIDX(idx)+1;
}

// 두 개의 자식 노드 중 높은 우선순위의 자식 노드 인덱스 값 반환
int GetHiPriChildIDX(Heap * ph, int idx)
{
   if(GetLChildIDX(idx)>ph->numOfData)
       return 0; //공집합 노드라는거 !
   else if(GetLChildIDX(idx)==ph->numOfData)
       return GetLChildIDX(idx); // 단말노드
   else
   {
       if(ph->heapArr[GetLChildIDX(idx)].pr>ph->heapArr[GetRChildIDX(idx)].pr)
           return GetRChildIDX(idx);
       else
           return GetLChildIDX(idx);
   }
}


// 힙에 데이터 저장
void HInsert(Heap * ph, HData data, priority pr)
{
   int idx = ph->numOfData+1;
   HeapElem nelem = {pr,data};
   
   while(idx!=1)
   {
       if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
       {
           ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
           idx = GetParentIDX(idx);
       }
       else
          break;
   }
          ph -> heapArr[idx]= nelem;
          ph-> numOfData += 1;
}

// 힙에서 데이터 삭제
HData HDelete(Heap * ph)
{
   HData retData = (ph->heapArr[1]).data;
   HeapElem lastElem = ph->heapArr[ph->numOfData];
   
   int parentIdx = 1;
   int childIdx;
   
   while(childIdx = GetHiPriChildIDX(ph, parentIdx))
   {
       if(lastElem.pr <= ph->heapArr[childIdx].pr)
           break;
       ph->heapArr[parentIdx] = ph->heapArr[childIdx];
       parentIdx = childIdx;
       
   }
   ph->heapArr[parentIdx] = lastElem;
   ph->numOfData-=1;
   return retData;
}

宣言関数の実装を支援する多くの有用なクラスがヘッダファイルに定義されています.GetHiPriChildIDX関数の実装を見てみましょう.

idx値が渡されると、ノードの2つのサブノードのうち優先度の高いインデックス値が返されます.

サブノードがない場合は0を返し、サブノードが1つしかない場合はインデックス値を返します.

int GetHiPriChildIDX(Heap * ph, int idx)
{
// 자식노드가 없다면! 
    if(GetLChildIDX(idx)>ph->numOfData)
        return 0; 
// 자식 노드가 왼쪽 하나라면         
    else if(GetLChildIDX(idx)==ph->numOfData)
        return GetLChildIDX(idx); // 단말노드
 //자식 모두 존재
    else
    {// 오른쪽 자식 노드의 우선순위가 더 크다면
        if(ph->heapArr[GetLChildIDX(idx)].pr>ph->heapArr[GetRChildIDX(idx)].pr)
            return GetRChildIDX(idx);
        else
        // 왼쪽이 더 크다면 ! 
            return GetLChildIDX(idx);
    }
}

もっとよく見てみましょう.

// 자식노드가 없다면! 
    if(GetLChildIDX(idx)>ph->numOfData)
        return 0; 

hipは完全バイナリツリーであるため,右側サブノードのみが存在することはない.
したがって,左側のサブノードがなければ,そのサブノードは存在しないと判断できる.
すなわち,サブノードが1つも存在しないノードが端末ノードである.
したがって,端末ノードの左側のサブノードの数はhipに格納されているノードの数を上回っている.
したがって、上記の演算文を使用して、サブノードがあるかどうかを確認できます.

// 자식 노드가 왼쪽 하나라면         
    else if(GetLChildIDX(idx)==ph->numOfData)
        return GetLChildIDX(idx); // 단말노드

唯一のサブノードは左のサブノードです.そしてこれがお尻の最後のノードです.
この言叶を见て、上のコードは完全に理解しているのではないでしょうか!?
HDelete関数を見てみましょう.
その前に、私たちは以下の判断を下すことができます.
「ルートノードに昇格した最後のノードは、自分の場所が見つかるまで下に移動します.しかし、このような頻繁な移動はコードに直接含める必要はありません.最終目的地が決定されると、一度にそこに移動できます.」

// 힙에서 데이터 삭제
HData HDelete(Heap * ph)
{
    HData retData = (ph->heapArr[1]).data; //번환을 위해서 삭제할 데이터 저장
    HeapElem lastElem = ph->heapArr[ph->numOfData]; // 힙의 마지막 노드 저장
    
    // parentIdx 에는 마지막 노드가 저장될 위치정보가 담긴다.
    int parentIdx = 1; // 루트노드가 위치해야 할 인덱스 값 저장
    int childIdx;
    
    //루트 노드의 우선순위가 높은 자식 노드를 시작으로 반복문 시작
    while(childIdx = GetHiPriChildIDX(ph, parentIdx))
    {
        if(lastElem.pr <= ph->heapArr[childIdx].pr) // 마지막 노드와 우선순위 비교
            break; // 마지막 노드의 우선순위가 높다면 반복문 탈출 !
        // 마지막 노드보다 우선순위가 높으니, 비교대상 노드의 위츠를 한 레벨 올린다.
        ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        parentIdx = childIdx; // 마지막 노드가 저장될 위치정보를 한 레벨 내림
        // 반복문 탈출하면 parentIdx에는 마지막 노드의 위치정보가 저장된다.
    }
    ph->heapArr[parentIdx] = lastElem; // 마지막 노드 최종 저장 
    ph->numOfData-=1;
    return retData;
}

parentIdxに格納されているインデックス値を更新し、最後のノードの場所を探しています.

Hinsert関数

挿入の過程を整理しましょう.
「新しいデータは最後の場所に保存されます.優先度が最も低いと仮定します.優先度の比較で自分の場所が見つかるまで上に移動します.」

// 힙에 데이터 저장
void HInsert(Heap * ph, HData data, priority pr)
{
    int idx = ph->numOfData+1; // 새 노드가 저장될 인덱스 값을 idx에 저장
    HeapElem nelem = {pr,data}; // 새 노드의 생성 및 초기화
    
    // 새 노드가 저장될 위치가 루트 노드의 위치가 아니라면 while문 반복
    while(idx!=1)
    {
        // 새 노드와 부모 노드의 우선순위 비교
        if(pr < (ph->heapArr[GetParentIDX(idx)].pr)) //새 노드의 우선순위가 더 높다면
        {
            // 부모 노드를 한 레벨 내린다.
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
            // 새 노드를 한 레벨 올린다.
            idx = GetParentIDX(idx);
        }
        else // 새 노드의 우선순위가 높지 않다면
           break;
    }
           ph -> heapArr[idx]= nelem; // 새 노드를 배열에 저장
           ph-> numOfData += 1;
}

Main関数

//
//  main.c
//  Heap
//

#include <stdio.h>
#include "SimpleHeap.h"

int main(void)
{
    Heap heap;
    HeapInit(&heap);
    
    HInsert(&heap, 'A', 1);
    HInsert(&heap, 'B', 2);
    HInsert(&heap, 'C', 3);
    printf("%c \n", HDelete(&heap));
    
    HInsert(&heap, 'A', 1);
    HInsert(&heap, 'B', 2);
    HInsert(&heap, 'C', 3);
    printf("%c \n",HDelete(&heap));
    
    while(!HIsEmpty(&heap))
        printf("%c \n", HDelete(&heap));
    
    return 0;
}

実行結果は、優先度の高い文字が最初に取り出されることを示しています.

私たちが実現した上のお尻は好評ですか?

私たちが体現するお尻がちょうど合っている場合、良い評価が期待できます.しかし、一般的には、良い評価が期待される点にも不足がある.
これは構造体の定義でまず発見できる.

typedef struct _heapElem
{
    Priority pr; // 값이 작을수록 높은 우선순위
    HData data;
}HeapElem;

上の構造体メンバーは、優先情報を含む変数を宣言します.
これは問題として指摘される可能性のある部分です.
もう一つの部分.

void HInsert(Heap * ph, HData data, Priority pr);
// 우선순위 정보도 넘겨라

これは.
データを入力する前に、自分で優先順位を決めて、値を私に伝えてください.はい.
私たちは以下のように抗弁しなければならない.
「ほとんどの場合、優先順位はデータを「公民」に決定する…優先順位の告知を求める決定基準でもない…優先順位を直接決定して告知することを要求する…?これも数字…?冗談でしょう…?
これらの問題を根本的に解決するために、お尻を変えましょう.