힙의 JavaScript 구현 방법에 대한 자세한 설명

힙의 정의

최대(최소) 힙은 각 노드의 키 값이 해당 하위 노드의 키 값(존재하는 경우)보다 작지(크지) 않은 트리입니다. ). 빅탑 힙은 완전 이진 트리이자 최대 트리이기도 합니다. 미니 힙은 완전한 이진 트리이자 최소 트리입니다.

또한 코드 작성 시 다음 두 가지 개념을 기억하는 것이 매우 중요합니다.

1. 상위 노드와 하위 노드의 관계: 정의 참조

2 . 완전 이진 트리: 참조 [2]

기본 작업

1. 빌드(힙 빌드)

2. 삽입(insertion) )

3. 삭제(삭제: 가장 작은 것 또는 가장 큰 것)

코드 구현

우선 2가지가 있다 코드 작성 전 매우 중요한 점 포인트:

1. 배열은 힙의 저장 구조로 사용될 수 있으며 이는 매우 간단하고 조작하기 쉽습니다.

2. In; 또한, 배열을 저장 구조로 사용하기 때문에 아버지와 아들의 관계는 인덱스를 기반으로 쉽게 찾을 수 있습니다.

JavaScript의 경우 배열 인덱스가 0부터 시작하면 관계는 다음과 같습니다.

nLeftIndex = 2 * (nFatherIndex+1) - 1;
nRightIndex = 2* (nFatherIndex+1);

이해하면 도움이 됩니다.

1. 왜냐하면 이는 배열이므로 상위 노드와 하위 노드 간의 관계를 유지하기 위해 특별한 구조가 필요하지 않습니다. 인덱스는 계산을 통해 얻을 수 있으므로 많은 문제가 발생하지 않습니다. 연결리스트 구조라면 훨씬 더 복잡해진다.

2. 완전 이진 트리의 개념은 [2]에서 참조할 수 있다. 다음 레이어가 채워지기 전에 왼쪽에서 오른쪽으로 이렇게 하면 전체 배열의 큰 영역을 이동할 필요가 없습니다. 이는 무작위 저장 구조(배열)의 단점이기도 합니다. 요소를 삭제한 후 전체 요소를 앞으로 이동하는 데 시간이 더 많이 걸립니다. 또한 이 기능을 사용하면 요소를 삭제할 때 힙이 트리의 루트 노드에 마지막 리프 노드를 추가하게 됩니다.

코드 구현:

/******************************************************
* file : 堆
* author : "page"
* time : "2016/11/02"
*******************************************************/
function Heap()
{
 this.data = [];
}
 
Heap.prototype.print = function () {
 console.log("Heap: " + this.data);
}
 
Heap.prototype.build = function(data){
 // 初始化
 this.data = [];
 if (!data instanceof Array)
 return false;
 
 // 入堆
 for (var i = 0; i < data.length; ++i) {
 this.insert(data[i]);
 }
 
 return true;
}
 
Heap.prototype.insert = function( nValue ){
 if (!this.data instanceof Array) {
 this.data = [];
 }
 
 this.data.push(nValue);
 // 更新新节点
 var nIndex = this.data.length-1;
 var nFatherIndex = Math.floor((nIndex-1)/2);
 while (nFatherIndex > 0){
 if (this.data[nIndex] < this.data[nFatherIndex]) {
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nFatherIndex];
 this.data[nFatherIndex] = temp;
 }
 
 nIndex = nFatherIndex;
 nFatherIndex = Math.floor((nIndex-1)/2);
 }
}
 
Heap.prototype.delete = function( ){
 if (!this.data instanceof Array) {
 return null;
 }
 
 var nIndex = 0;
 var nValue = this.data[nIndex];
 var nMaxIndex = this.data.length-1;
 // 更新新节点
 var nLeaf = this.data.pop();
 this.data[nIndex] = nLeaf;
 
 while (nIndex < nMaxIndex ){
 var nLeftIndex = 2 * (nIndex+1) - 1;
 var nRightIndex = 2 * (nIndex+1);
 
 // 找最小的一个子节点(nLeftIndex < nRightIndex)
 var nSelectIndex = nLeftIndex;
 if (nRightIndex < nMaxIndex) {
 nSelectIndex = (this.data[nLeftIndex] > this.data[nRightIndex]) ? nRightIndex : nLeftIndex;
 }
 
 if (nSelectIndex < nMaxIndex && this.data[nIndex] > this.data[nSelectIndex] ){
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nSelectIndex];
 this.data[nSelectIndex] = temp;
 }
 
 nIndex = nSelectIndex;
 }
 
 return nValue;
}
// test
var heap = new Heap();
heap.build([1, 3, 5, 11, 4, 6, 7, 12, 15, 10, 9, 8]);
heap.print();
// insert
heap.insert(2);
heap.print();
// delete
heap.delete();
heap.print();

JavaScript에 대한 요약

여기에 객체지향 구현 방법이 있습니다. 더 좋은 표현 방법과 작성 방법이 있는지는 모르겠습니다. ;

배열의 여러 사용법을 배웠습니다. 푸시 및 팝 작업은 사용하기 매우 쉽습니다.

배열을 판단하는 방법도 인터넷에서 일시적으로 검색되었습니다. instanceof ) 별로 인상적이지 않습니다. 사용하지 않으면 다음에 잊어버릴 수도 있습니다.

참고

[1] "데이터 구조 및 알고리즘 분석: C 언어 설명"

[2] 그래픽 데이터 구조(8) - 바이너리 힙

[3]>데이터 구조: 힙

요약

JavaScript의 배열은 푸시 및 팝 작업을 구현하며, 다른 많은 언어도 유사한 데이터 구조 및 작업(예: C++의 Vector)이며 임의 작업도 지원합니다. 그래서 이러한 구조에 단순히 자동정렬이라는 개념만 추가하면 힙을 쉽게 풀 수 있지 않을까 하는 생각이 들었습니다. 나중에 C++ STL의 make_heap을 보고 제가 아는 것이 너무 적다는 것을 깨달았습니다. 내 생각이 맞았다니 다행이다. JavaScript를 확인하지 않았는데, 존재하거나 구현하기 쉬운 것 같아요.

직접 구현해 본 결과 이 ​​구조도 한 번만 사용해 볼 의향이 있으면 매우 간단하다는 것을 알았습니다. ;

저는 아직 JavaScript의 세부 사항에 대해 많이 알지 못합니다. 예를 들어, 배열을 사용하려면 아직 JavaScript의 핵심을 다루지 않았습니다. , 그리고 본질은 지속적인 학습과 연습이 필요합니다.

이 코드는 프로그래밍의 개념과 기본을 이해하면 작성할 수 있습니다. 그러나 코드를 더 간결하게 작성할 수 있습니다. 예를 들어 삭제 함수가 가장 작은 자식 노드를 찾으면 왼쪽 노드와 오른쪽 노드의 인덱스를 비교할 필요가 없습니다. 코드 부분은 계속해서 최적화되고 간소화될 수 있는 것처럼 느껴집니다.