如何根據(jù)一個(gè)數(shù)組建立最大堆

最大堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最大者的堆。 最小堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最小者的堆。 而最大-最小堆集結(jié)了最大堆和最小堆的優(yōu)點(diǎn)，這也是其名字的由來。 最大-最小堆是最大層和最小層交替出現(xiàn)的二叉樹，即最大層結(jié)點(diǎn)的兒子屬于最小層，最小層結(jié)點(diǎn)的兒子屬于最大層。 以最大（小）層結(jié)n點(diǎn)為根結(jié)點(diǎn)的子樹保有最大（?。┒研再|(zhì)：根結(jié)點(diǎn)的鍵值為該子樹結(jié)點(diǎn)鍵值中最大（?。╉?xiàng)。 主要操作不失一般性，只討論根結(jié)點(diǎn)為最小層的情況。插入 只需要將節(jié)點(diǎn)插在二叉樹的最后一個(gè)葉子結(jié)點(diǎn)位置，然后比較它對(duì)它父親節(jié)點(diǎn)的大小，如果大則停止；如果小則交換位置，然后對(duì)父親節(jié)點(diǎn)遞歸該過程直至根節(jié)點(diǎn)。復(fù)雜度為O(log(n))。 一般來說，插入的位置可以不是最后一個(gè)葉子節(jié)點(diǎn)，可以作為任意中間節(jié)點(diǎn)的孩子節(jié)點(diǎn)插入，將這個(gè)葉子節(jié)點(diǎn)變?yōu)橹虚g節(jié)點(diǎn)后，按上文所說的方法調(diào)整節(jié)點(diǎn)順序以保證維持堆特性不變。刪除 要從堆中刪除一個(gè)節(jié)點(diǎn)，用最后一個(gè)節(jié)點(diǎn)替換掉根節(jié)點(diǎn)，然后調(diào)整節(jié)點(diǎn)順序以維持堆特性。建堆既可以用堆調(diào)整方法將原數(shù)組調(diào)整為一個(gè)堆，也可以借助往堆中插入元素的方法從無到有的建立一個(gè)堆。兩種方法比較：（1）借助堆調(diào)整建堆的時(shí)間復(fù)雜度為O(n)。借助插入法建堆的時(shí)間復(fù)雜度為O(nlgn) ，書上第二問要求證明這個(gè)復(fù)雜度，但是我認(rèn)為插入法的復(fù)雜度也是O（n），因?yàn)樗投颜{(diào)整的區(qū)別在于針對(duì)每個(gè)節(jié)點(diǎn)i，堆調(diào)整是自上向下進(jìn)行調(diào)整，插入法是自下向上進(jìn)行調(diào)整。（2）對(duì)于同樣的輸入兩個(gè)方法建立的堆可能不同。因?yàn)槎颜{(diào)整時(shí)，是i要跟它的兩個(gè)子女進(jìn)行比較，選出最大（小）的，但是插入x時(shí)，x只跟它的父節(jié)點(diǎn)進(jìn)行比較。比如輸入為2、3、4，堆調(diào)整建堆為4、3、2，插入法建堆為4、2、3。插入法建最大堆代碼如下：

西城ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書未來市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18982081108（備注：SSL證書合作）期待與您的合作！

public static void split(String source,int num) throws Exception{ int k=0; String temp="";

Java面向?qū)ο?/p>

1. super()與this()的區(qū)別？

This（）：當(dāng)前類的對(duì)象,super父類對(duì)象。

Super（）：在子類訪問父類的成員和行為,必須受類繼承規(guī)則的約束

而this他代表當(dāng)前對(duì)象,當(dāng)然所有的資源都可以訪問.

在構(gòu)造函數(shù)中,如果第一行沒有寫super(),編譯器會(huì)自動(dòng)插入.但是如果父類沒有不帶參數(shù)的構(gòu)造函數(shù),或這個(gè)函數(shù)被私有化了(用private修飾).此時(shí)你必須加入對(duì)父類的實(shí)例化構(gòu)造.而this就沒有這個(gè)要求,因?yàn)樗旧砭瓦M(jìn)行實(shí)例化的構(gòu)造.

而在方法中super和this使用的方法就差不多了.只不過super 要考慮是否能訪問其父類的資源.

2. 作用域public,protected,private,以及不寫時(shí)的區(qū)別？

Public:不同包、 同一包、 類內(nèi)都可用

Private： 類內(nèi)

Protected:不同包的子類、同一包、 類內(nèi)都可用

不寫時(shí): 同一包內(nèi)、類內(nèi)

3. 編程輸出如下圖形。

* * * * *

* * * *

* * *

* *

*

代碼如下：

public class Print {

publicstatic void main(String[] args) {

for(int i = 0; i 5; i++) {

for(int j = 5; j i; j--) {

System.out.print("*");

}

System.out.println();

}

}

}

4. JAVA的事件委托機(jī)制和垃圾回收機(jī)制

Java事件委托機(jī)制的概念,一個(gè)源產(chǎn)生一個(gè)事件并將它送到一個(gè)或多個(gè)監(jiān)聽器那里。在這種方案中，監(jiān)聽器簡(jiǎn)單的等待，直到它收到一個(gè)事件。一旦事件被接受，監(jiān)聽器將處理這個(gè)事件，然后返回。

垃圾回收機(jī)制垃圾收集是將分配給對(duì)象但不再使用的內(nèi)存回收或釋放的過程。如果一個(gè)對(duì)象沒有指向它的引用或者其賦值為null,則次對(duì)象適合進(jìn)行垃圾回收

5. 在JAVA中，如何跳出當(dāng)前的多重嵌套循環(huán)？

用break; return 方法。

6. 什么是java序列化，如何實(shí)現(xiàn)java序列化？(寫一個(gè)實(shí)例)

序列化:處理對(duì)象流的機(jī)制，所謂對(duì)象流也就是將對(duì)象的內(nèi)容進(jìn)行流化?？梢詫?duì)流化后的對(duì)象進(jìn)行讀寫操作，也可將流化后的對(duì)象傳輸于網(wǎng)絡(luò)之間。序列化是為了解決在對(duì)對(duì)象流進(jìn)行讀寫操作時(shí)所引發(fā)的問題。

序列化的實(shí)現(xiàn)：將需要被序列化的類實(shí)現(xiàn)Serializable接口，該接口沒有需要實(shí)現(xiàn)的方法，implementsSerializable只是為了標(biāo)注該對(duì)象是可被序列化的，然后使用一個(gè)輸出流(如：FileOutputStream)來構(gòu)造一個(gè)ObjectOutputStream(對(duì)象流)對(duì)象，接著，使用ObjectOutputStream對(duì)象的writeObject(Object obj)方法就可以將參數(shù)為obj的對(duì)象寫出(即保存其狀態(tài))，要恢復(fù)的話則用輸入流。

7. 一個(gè)".java"源文件中是否可以包括多個(gè)類（不是內(nèi)部類）？有什么限制？

可以。如果這個(gè)類的修飾符是public，其類名與文件名必須相同。

8. 排序都有哪幾種方法？請(qǐng)列舉。用JAVA實(shí)現(xiàn)一個(gè)快速排序？

排序的方法有：插入排序（直接插入排序、希爾排序），交換排序（冒泡排序、快速排序），選擇排序（直接選擇排序、堆排序），歸并排序，分配排序（箱排序、基數(shù)排序）

快速排序的偽代碼。

9. Overload和Override的區(qū)別。Overloaded的方法是否可以改變返回值的類型?

重寫Override，子類覆蓋父類的方法，將子類傳與父類的引用調(diào)用的還是子類的方法。

重載Overloading 一個(gè)類多個(gè)方法，名稱相同，參數(shù)個(gè)數(shù)類型不同。

兩者都是Java多態(tài)性的不同表現(xiàn)。

Overloaded的方法是可以改變返回值的類型。

1， public class Ctest(){

Public static void main(){

System.out.prinln(8+8+”88”+8+8);

}

} 168888

（方法的重寫Overriding和重載Overloading是Java多態(tài)性的不同表現(xiàn)。重寫Overriding是父類與子類之間多態(tài)性的一種表現(xiàn)，重載Overloading是一個(gè)類中多態(tài)性的一種表現(xiàn)。如果在子類中定義某方法與其父類有相同的名稱和參數(shù)，我們說該方法被重寫 (Overriding)。子類的對(duì)象使用這個(gè)方法時(shí)，將調(diào)用子類中的定義，對(duì)它而言，父類中的定義如同被“屏蔽”了。如果在一個(gè)類中定義了多個(gè)同名的方法，它們或有不同的參數(shù)個(gè)數(shù)或有不同的參數(shù)類型，則稱為方法的重載(Overloading)。

Overloaded的方法是可以改變返回值的類型。）

10. Final類有什么特點(diǎn)？

屬性常量 方法不可以overridding 類不可以繼承

11. 繼承時(shí)候類的執(zhí)行順序問題,一般都是選擇題,問你將會(huì)打印出什么?

答:父類：

package test;

public class FatherClass {

public FatherClass() {

System.out.println("FatherClassCreate");

}

}

子類:

package test;

import test.FatherClass;

public class ChildClass extends FatherClass{

public ChildClass() {

System.out.println("ChildClassCreate");

}

public static void main(String[] args) {

FatherClass fc = new FatherClass();

ChildClass cc = new ChildClass();

}

}

輸出結(jié)果：

C:java test.ChildClass

FatherClass Create

FatherClass Create

ChildClass Create

12. 內(nèi)部類的實(shí)現(xiàn)方式?

package test;

public class OuterClass {

private class InterClass {

Public Interlass(){

System.out.println("InterClassCreate");

}

}

public OuterClass(){

InterClass ic = new InterClass();

System.out.println("OuterClassCreate");

}

public static void main(String[] args){

OuterClass oc = new OuterClass();

}

}

輸出結(jié)果:

C:java test/OuterClass InterClass Create OuterClass Create

13. 用JAVA實(shí)現(xiàn)一種排序，JAVA類實(shí)現(xiàn)序列化的方法(二種)？

14. 如在COLLECTION框架中，實(shí)現(xiàn)比較要實(shí)現(xiàn)什么樣的接口？

15. 用插入法進(jìn)行排序代碼如下

package test;

import java.util.*;

class InsertSort {

ArrayList al;

public InsertSort(int num,int mod) {

al = new ArrayList(num);

Random rand = new Random();

System.out.println("The ArrayList SortBefore:");

for (int i=0;inum ;i++ ){

al.add(new Integer(Math.abs(rand.nextInt())% mod + 1));

System.out.println("al["+i+"]="+al.get(i));

}

}

public void SortIt(){

Integer tempInt;

int MaxSize=1;

for(int i=1;ial.size();i++){

tempInt = (Integer)al.remove(i);

if(tempInt.intValue()=((Integer)al.get(MaxSize-1)).intValue()){

al.add(MaxSize,tempInt);

MaxSize++;

System.out.println(al.toString());

} else {

for (int j=0;jMaxSize ;j++ ){

if(((Integer)al.get(j)).intValue()=tempInt.intValue()){

al.add(j,tempInt);

MaxSize++;

System.out.println(al.toString());

break;

}

}

}

}

System.out.println("The ArrayList SortAfter:");

for(int i=0;ial.size();i++) {

System.out.println("al["+i+"]="+al.get(i));

}

}

public static void main(String[] args) {

InsertSort is = new InsertSort(10,100);

is.SortIt();

}

}

JAVA類實(shí)現(xiàn)序例化的方法是實(shí)現(xiàn)java.io.Serializable接口

Collection框架中實(shí)現(xiàn)比較要實(shí)現(xiàn)Comparable 接口和 Comparator 接口

16. 編程：編寫一個(gè)截取字符串的函數(shù)，輸入為一個(gè)字符串和字節(jié)數(shù)，輸出為按字節(jié)截取的字符串。但是要保證漢字不被截半個(gè)，如"我ABC"4，應(yīng)該截為"我AB"，輸入"我ABC漢DEF"，6，應(yīng)該輸出為"我ABC"而不是"我ABC+漢的半個(gè)"。

public static void split(String source,intnum) throws Exception{

intk=0;

Stringtemp="";

for(int i = 0; i source.length(); i++){

byte[]b=(source.charAt(i)+"").getBytes();

k=k+b.length;

if(knum){

break;

}

temp=temp+source.charAt(i);

}

System.out.println(temp);

}

15、Java編程,打印昨天的當(dāng)前時(shí)刻

public class YesterdayCurrent{

public void main(String[] args){

Calendar cal = Calendar.getInstance();

cal.add(Calendar.DATE, -1);

System.out.println(cal.getTime());

}

}

16、文件讀寫,實(shí)現(xiàn)一個(gè)計(jì)數(shù)器

public int getNum(){

int i = -1;

try{

String stri="";

BufferedReader in = new BufferedReader(newFileReader(f));

while((stri=in.readLine())!=null){

i = Integer.parseInt(stri.trim());

}

in.close();

}catch(Exception e){

e.printStackTrace();

}

return i;

}

public void setNum(){

int i = getNum();

i++;

try{

PrintWriter out=new PrintWriter(newBufferedWriter(new FileWriter(f,false)));

out.write(String.valueOf(i)); //可能是編碼的原因，如果直接寫入int的話，將出現(xiàn)java編碼和windows編碼的混亂，因此此處寫入的是String

out.close() ;

}catch(Exception e){

e.printStackTrace();

}

}

17、指出下面程序的運(yùn)行結(jié)果。

class A{

static{

System.out.print("1");

}

public A(){

System.out.print("2");

}

}

class B extends A{

static{

System.out.print("a");

}

public B(){

System.out.print("b");

}

}

public class Hello{

public static void main(String[] ars){

A ab = new B(); //執(zhí)行到此處,結(jié)果: 1a2b

ab = new B(); //執(zhí)行到此處,結(jié)果: 1a2b2b

}

}注:類的static 代碼段,可以看作是類首次加載(被虛擬機(jī)加載)執(zhí)行的代碼,而對(duì)于類的加載,首先要執(zhí)行其基類的構(gòu)造,再執(zhí)行其本身的構(gòu)造

18、抽象類和接口的區(qū)別？

(1)接口可以被多重implements,抽象類只能被單一extends(2)接口只有定義,抽象類可以有定義和實(shí)現(xiàn)(3)接口的字段定義默認(rèn)為:publicstatic final, 抽象類字段默認(rèn)是"friendly"(本包可見)

當(dāng)功能需要累積時(shí)用抽象類，不需要累積時(shí)用接口。

19、什么是類的反射機(jī)制?

通過類(Class對(duì)象)，可以得出當(dāng)前類的fields、method、construtor、interface、superClass、modified等，同是可以通過類實(shí)例化一個(gè)實(shí)例、設(shè)置屬性、喚醒方法。Spring中一切都是返射、struts、hibernate都是通過類的返射進(jìn)行開發(fā)的。

20、類的返射機(jī)制中的包及核心類?

①java.lang.Class②java.lang.refrection.Method③java.lang.refrection.Field

④java.lang.refrection.Constructor⑤java.lang.refrection.Modifier⑥java.lang.refrection.Interface

21、得到Class的三個(gè)過程是什么?

①對(duì)象.getClass()②類.class或Integer.type(int) Integer.class(java.lang.Integer)③Class.forName();

22、如何喚起類中的一個(gè)方法？

①產(chǎn)生一個(gè)Class數(shù)組，說明方法的參數(shù)②通過Class對(duì)象及方法參數(shù)得到Method③通過method.invoke(實(shí)例,參數(shù)值數(shù)組)喚醒方法

23、如何將數(shù)值型字符轉(zhuǎn)換為數(shù)字（Integer，Double）？

Integer.parseInt(“1234”) Double.parseDouble(“123.2”)

24、如何將數(shù)字轉(zhuǎn)換為字符？

1+”” 1.0+””

25、如何去小數(shù)點(diǎn)前兩位，并四舍五入。

double d=1256.22d; d=d/100; System.out.println(Math.round(d)*100);

26、如何取得年月日，小時(shí)分秒？

Calendar c=Calendar.getInstance();

c.set(Calendar.YEAR,2004);

c.set(Calendar.MONTH,0);

c.set(Calendar.DAY_OF_MONTH,31);

System.out.println(c.get(Calendar.YEAR)+" "+(c.get(Calendar.MONTH)+1)+" "+c.get(Calendar.DAY_OF_MONTH));

27、如何取得從1970年到現(xiàn)在的毫秒數(shù)

Java.util.Date dat=new Date(); long now=dat.getTime();

或System.currentTimeMillis()

28、如何獲取某個(gè)日期是當(dāng)月的最后一天？

當(dāng)前日期加一天，若當(dāng)前日期與結(jié)果的月份不相同，就是最后一天。

取下一個(gè)月的第一天，下一個(gè)月的第一天-1

public static void main(String[] args){

Calendarc=Calendar.getInstance();

c.set(Calendar.YEAR,2004);

c.set(Calendar.MONTH,0);

c.set(Calendar.DAY_OF_MONTH,30);

Calendarc1=(Calendar)c.clone();

System.out.println(c.get(Calendar.YEAR)+""+(c.get(Calendar.MONTH)+1)+" "+c.get(Calendar.DAY_OF_MONTH));

c.add(Calendar.DAY_OF_MONTH,1);

if(c.get(Calendar.MONTH)!=c1.get(Calendar.MONTH)){

System.out.println("是最后一天");

}else{

System.out.println("不是取后一天");

}

}

29、如何格式化日期？

Import java.text. SimpleDateFormat;

SimpleDateFormat sdf=newSimpleDateFormat("yyyy-MM-dd hh:mm:ss");

Date dat=new Date();

String str=sdf.format(dat); //把日期轉(zhuǎn)化為字符串

System.out.println(str);

Java.util.Date d1=sdf.parse(“yyyy-mm-dd”); //將字符串轉(zhuǎn)化為日期

30、編碼轉(zhuǎn)換，怎樣實(shí)現(xiàn)將GB2312編碼的字符串轉(zhuǎn)換為ISO-8859-1編碼的字符串。

String a=new String("中".getBytes("gb2312"),"iso-8859-1");

String a=new String("中".getBytes("iso-8859-1"));

應(yīng)該是String a=new String("中".getBytes("gb2312"),"iso-8859-1");

String a1=newString(a.getBytes("iso-8859-1"));

插入法排序

用插入法進(jìn)行排序代碼如下

package test;

import java.util.*;

class InsertSort

{

ArrayList al;

public InsertSort(int num,int mod)

{

al = new ArrayList(num);

Random rand = new Random();

System.out.println("The ArrayList Sort Before:");

for (int i=0;inum ;i++ )

{

al.add(new Integer(Math.abs(rand.nextInt()) % mod + 1));

System.out.println("al["+i+"]="+al.get(i));

}

}

public void SortIt()

{

Integer tempInt;

int MaxSize=1;

for(int i=1;ial.size();i++)

{

tempInt = (Integer)al.remove(i);

if(tempInt.intValue()=((Integer)al.get(MaxSize-1)).intValue())

{

al.add(MaxSize,tempInt);

MaxSize++;

System.out.println(al.toString());

} else {

for (int j=0;jMaxSize ;j++ )

{

if

(((Integer)al.get(j)).intValue()=tempInt.intValue())

{

al.add(j,tempInt);

MaxSize++;

System.out.println(al.toString());

break;

}

}

}

}

System.out.println("The ArrayList Sort After:");

for(int i=0;ial.size();i++)

{

System.out.println("al["+i+"]="+al.get(i));

}

}

public static void main(String[] args)

{

InsertSort is = new InsertSort(10,100);

is.SortIt();

}

}

JAVA類實(shí)現(xiàn)序例化的方法是實(shí)現(xiàn)java.io.Serializable接口

Collection框架中實(shí)現(xiàn)比較要實(shí)現(xiàn)Comparable 接口和 Comparator 接口

用JAVA編寫插入法對(duì)一個(gè)給定數(shù)組進(jìn)行升序排序的方法

//用冒泡，就是for循環(huán)里加if判斷就行了。

class Test{

public static void main(String [] args){

int a[10]={2,1,4,5,6,7,8,9,23,44};

for (i=0;ia.length;i++)

{

for (j=0;ja.length-1-i;j++)

{

if (a[j]a[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

for (i=0;ia.length;i++){

System.out.println(a[i]);

}

}

}

文章標(biāo)題：插入法堆的java代碼的簡(jiǎn)單介紹
文章地址：http://jinyejixie.com/article34/doseese.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、App開發(fā)、面包屑導(dǎo)航、網(wǎng)站內(nèi)鏈、響應(yīng)式網(wǎng)站、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)