So bestimmen Sie die Heap-Sequenz

Wir kennen eine Sequenz wie {100,6070,50,32,65}. Wie können wir feststellen, ob es sich um einen Heap handelt?

Antwort: Stellen Sie sich diese Sequenz als einen binären Baum vom Array-Typ vor. Wenn der Wurzelknoten i ist, ist der linke Teilbaum 2*i und der rechte Teilbaum ist 2*i+1.

Der Heap ist in einen maximalen Heap und einen minimalen Heap unterteilt.

1. Alle übergeordneten Knoten im maximalen Heap sind größer als der linke Teilbaum und der rechte Teilbaum. Wenn beispielsweise eine bekannte Sequenz als Heap gezeichnet wird:

Die bekannte Sequenz ist also ein maximaler Heap.

2. Alle übergeordneten Knoten im minimalen Heap sind kleiner als der linke Teilbaum und der rechte Teilbaum, z. B. {32,50,60,70,100,65}, gezeichnet als Heap:

Die Sequenz, die die beiden oben genannten Situationen erfüllt, ist ein Haufen

Das obige ist der detaillierte Inhalt vonSo bestimmen Sie die Heap-Sequenz. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!