John William Joseph (Bill) Williams (September 1930 â 29 September 2012) was a computer scientist best known for inventing heapsort and the binary heap data structure in 1963 while working for Elliot Bros. (London) Ltd.
He was born in England, specifically in the district Chippenham in the county Wiltshire, to William Henry Williams and Mrs. Haines. During the 1939 Register, he lived at 12 The Vicarage St Mary Street, Chippenham M.B., Wiltshire, England with Joseph Haines (born 1871), Eva F Williams (born 1903), and William H Williams (born 1883).
Eva Florence Haines (born in Chippenham) was the daughter of Joseph Haines and Florence Ellen Light (born circa 1884). 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.
On 3 March 1962, John William Joseph Williams (mathematician, age 31) married Ann Zerny (nurse, age 23) at Christ Church in Chorleywood Parish in Hertfordshire County. They had children named Peter (Carey), Rob (Rick) and Richard (Charlotte), who had children named Rowan, Derek, Emmett, Reed, and Seth.
In 1974, he moved to Ottawa, Ontario, Canada. On 10 June 1994, he was living at 18 Banting Crescent, Kanata, Ontario, Canada K2K 1P4. He volunteered for Kanata Theatre, helping construct sets, design lighting, and occasionally act on stage.
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.
In 1952, he received a B.Sc. in mathematics from King's College, University of London.
In England, he worked as a programmer for Elliot Automation, 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. He also worked for English Electric and GEC. 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.
After moving to Canada in 1974, he worked for Bell-Northern Research Ltd., Ottawa (BNR) and Northern Telecom (Nortel) until retiring in 1995. 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. On 10 March 1988, Northern Telecom (retroactively initially Bell-Northern Research) filed a US, and subsequently international, patent for a "Digital Key Telephone System", listing him as an inventor. In 1992, he told Andre Vellino of Nortel Networks that "Design is the art of defining a system to meet a set of constraints".