J. W. J. Williams

John William Joseph (Bill) Williams^[1] (September^[2][3] 1930 – 29 September 2012)^[3][4] was a computer scientist best known for inventing heapsort and the binary heap data structure in 1963 while working for Elliot Bros. (London) Ltd.^[5][6][7][8]

Personal life

He was born in England,^[9] specifically in the district Chippenham in the county Wiltshire,^[2] to William Henry Williams^[4] and Mrs. Haines.^[2] During the 1939 Register, he lived at 12 The Vicarage St Mary Street, Chippenham M.B., Wiltshire, England^[10] with Joseph Haines (born 1871), Eva F Williams (born 1903), and William H Williams (born 1883).^[11]

Eva Florence Haines (born in Chippenham) was the daughter of Joseph Haines and Florence Ellen Light (born circa 1884).^[12][13][14] William H Williams (born 23 July 1883) and Eva Florence Haines (born 13 March 1903) were married on 29 January 1929 in Chippenham, Wiltshire, England.^[12][15][16]

On 3 March 1962, John William Joseph Williams (mathematician,^[9] age 31) married Ann^[3][6] Zerny (nurse,^[6] age 23) at Christ Church in Chorleywood Parish in Hertfordshire County.^[4] They had children named Peter (Carey), Rob (Rick) and Richard (Charlotte), who had children named Rowan, Derek, Emmett, Reed, and Seth.^[3]

In 1974, he moved to Ottawa, Ontario, Canada.^[3][6][9] On 10 June 1994, he was living at 18 Banting Crescent, Kanata, Ontario, Canada K2K 1P4.^[1] He volunteered for Kanata Theatre, helping construct sets, design lighting, and occasionally act on stage.^[3]

On 29 September 2012, he died at age 82; on 6 October, he had a Celebration of Life at the Ron Maslin Playhouse, requesting donations in his memory to be given to Kanata Theatre and Ottawa Heart Institute.^[3]

Career

In 1952, he received a B.Sc. in mathematics from King's College, University of London.^[9]

In England, he worked as a programmer for Elliot Automation,^[9] formerly Elliot Brothers (London) Limited, where he invented heapsort and used it to create the event-driven Elliott Simulator Package (ESP) with the help of C. A. R. (Tony) Hoare.^[5][6][17] He also worked for English Electric and GEC.^[9] He worked with Donald E. Knuth to develop a two-heap data structure that they called a "priority deque", published as an exercise in The Art of Computer Programming in 1973.^[18][19]

After moving to Canada in 1974, he worked for Bell-Northern Research Ltd., Ottawa (BNR) and Northern Telecom (Nortel) until retiring in 1995.^[3][6] At BNR, he worked on various software and hardware systems such as the DMS-100 digital telephone switch, publishing a paper about their software in June 1982.^[9] On 10 March 1988, Northern Telecom (retroactively initially Bell-Northern Research^[20]) filed a US, and subsequently international, patent for a "Digital Key Telephone System", listing him as an inventor.^{[21][22][23][1]} In 1992, he told Andre Vellino of Nortel Networks that "Design is the art of defining a system to meet a set of constraints".^[24]